<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>链表 | 房飞跃的博客</title>
    <meta name="generator" content="VuePress 1.8.2">
    <link rel="apple-touch-icon" href="/apple-touch-icon.png">
    <link rel="icon" href="/favicon.ico">
    <link rel="manifest" href="/manifest.json">
    <meta name="description" content="房飞跃的博客">
    <meta name="theme-color" content="#ffffff">
    
    <link rel="preload" href="/assets/css/0.styles.e57fdc06.css" as="style"><link rel="preload" href="/assets/js/app.8c5a7a92.js" as="script"><link rel="preload" href="/assets/js/2.8e30e130.js" as="script"><link rel="preload" href="/assets/js/6.0db48d19.js" as="script"><link rel="preload" href="/assets/js/64.0323ed89.js" as="script"><link rel="prefetch" href="/assets/js/10.e695640a.js"><link rel="prefetch" href="/assets/js/100.fae9757f.js"><link rel="prefetch" href="/assets/js/101.d26f7a9a.js"><link rel="prefetch" href="/assets/js/102.e9b20f43.js"><link rel="prefetch" href="/assets/js/103.6d251ff3.js"><link rel="prefetch" href="/assets/js/104.5de918be.js"><link rel="prefetch" href="/assets/js/105.aead61a1.js"><link rel="prefetch" href="/assets/js/106.09a5decb.js"><link rel="prefetch" href="/assets/js/107.a44fc48a.js"><link rel="prefetch" href="/assets/js/108.cec63522.js"><link rel="prefetch" href="/assets/js/109.db1a4ed7.js"><link rel="prefetch" href="/assets/js/11.769ac82c.js"><link rel="prefetch" href="/assets/js/110.10914d38.js"><link rel="prefetch" href="/assets/js/111.2c0ddf25.js"><link rel="prefetch" href="/assets/js/112.c792ca07.js"><link rel="prefetch" href="/assets/js/113.a769ad8f.js"><link rel="prefetch" href="/assets/js/114.c1dca6a0.js"><link rel="prefetch" href="/assets/js/115.82e1fb4f.js"><link rel="prefetch" href="/assets/js/116.c927762b.js"><link rel="prefetch" href="/assets/js/117.5c14eedf.js"><link rel="prefetch" href="/assets/js/118.24861bb6.js"><link rel="prefetch" href="/assets/js/119.3fafaebf.js"><link rel="prefetch" href="/assets/js/12.23031504.js"><link rel="prefetch" href="/assets/js/120.a9ff8fae.js"><link rel="prefetch" href="/assets/js/121.3eb4b3a1.js"><link rel="prefetch" href="/assets/js/122.ff06cffe.js"><link rel="prefetch" href="/assets/js/123.aaf767a6.js"><link rel="prefetch" href="/assets/js/124.4daf257a.js"><link rel="prefetch" href="/assets/js/125.e7e71d3f.js"><link rel="prefetch" href="/assets/js/126.cdee6d86.js"><link rel="prefetch" href="/assets/js/127.aa133c3f.js"><link rel="prefetch" href="/assets/js/128.a8e7d8b2.js"><link rel="prefetch" href="/assets/js/129.dcca2d84.js"><link rel="prefetch" href="/assets/js/13.f37f647e.js"><link rel="prefetch" href="/assets/js/130.3925fb20.js"><link rel="prefetch" href="/assets/js/131.a3a759ed.js"><link rel="prefetch" href="/assets/js/132.84bb9bf9.js"><link rel="prefetch" href="/assets/js/133.30fceda7.js"><link rel="prefetch" href="/assets/js/134.e02f66bf.js"><link rel="prefetch" href="/assets/js/135.71a35d7f.js"><link rel="prefetch" href="/assets/js/136.77762773.js"><link rel="prefetch" href="/assets/js/137.b9741de3.js"><link rel="prefetch" href="/assets/js/138.59b64aa0.js"><link rel="prefetch" href="/assets/js/139.d81e68a1.js"><link rel="prefetch" href="/assets/js/14.0091824d.js"><link rel="prefetch" href="/assets/js/140.68388ddb.js"><link rel="prefetch" href="/assets/js/141.e69cc877.js"><link rel="prefetch" href="/assets/js/142.65fc1806.js"><link rel="prefetch" href="/assets/js/143.4f1e9b3d.js"><link rel="prefetch" href="/assets/js/144.5cf4bdda.js"><link rel="prefetch" href="/assets/js/145.1a1cdb18.js"><link rel="prefetch" href="/assets/js/146.ef4fe2c3.js"><link rel="prefetch" href="/assets/js/147.f5e5d206.js"><link rel="prefetch" href="/assets/js/148.07c7208f.js"><link rel="prefetch" href="/assets/js/149.fb71df8d.js"><link rel="prefetch" href="/assets/js/15.4e1991f3.js"><link rel="prefetch" href="/assets/js/150.771bcbfe.js"><link rel="prefetch" href="/assets/js/151.de02cd55.js"><link rel="prefetch" href="/assets/js/152.6a5b243d.js"><link rel="prefetch" href="/assets/js/153.c1c426d2.js"><link rel="prefetch" href="/assets/js/154.51e08a99.js"><link rel="prefetch" href="/assets/js/155.ab801c7a.js"><link rel="prefetch" href="/assets/js/156.e62111f0.js"><link rel="prefetch" href="/assets/js/157.67f19eb7.js"><link rel="prefetch" href="/assets/js/158.3e57553c.js"><link rel="prefetch" href="/assets/js/159.f01ea56a.js"><link rel="prefetch" href="/assets/js/16.aafe549d.js"><link rel="prefetch" href="/assets/js/160.81468500.js"><link rel="prefetch" href="/assets/js/161.8341c4c9.js"><link rel="prefetch" href="/assets/js/162.18cd1d1e.js"><link rel="prefetch" href="/assets/js/163.2ed65e27.js"><link rel="prefetch" href="/assets/js/164.1c0adbfd.js"><link rel="prefetch" href="/assets/js/165.4382f96e.js"><link rel="prefetch" href="/assets/js/166.47ad10ec.js"><link rel="prefetch" href="/assets/js/167.ee3e3de3.js"><link rel="prefetch" href="/assets/js/168.1273ebb0.js"><link rel="prefetch" href="/assets/js/169.bb6578e0.js"><link rel="prefetch" href="/assets/js/17.4548c40c.js"><link rel="prefetch" href="/assets/js/170.6aef0437.js"><link rel="prefetch" href="/assets/js/171.4818ad12.js"><link rel="prefetch" href="/assets/js/172.7f4674ed.js"><link rel="prefetch" href="/assets/js/173.25951cfa.js"><link rel="prefetch" href="/assets/js/174.604b8889.js"><link rel="prefetch" href="/assets/js/175.752d6221.js"><link rel="prefetch" href="/assets/js/176.ee6ccaf2.js"><link rel="prefetch" href="/assets/js/177.df3e7548.js"><link rel="prefetch" href="/assets/js/178.0c05bdea.js"><link rel="prefetch" href="/assets/js/179.fa300396.js"><link rel="prefetch" href="/assets/js/18.4a166581.js"><link rel="prefetch" href="/assets/js/180.78580e5a.js"><link rel="prefetch" href="/assets/js/181.c08c58e9.js"><link rel="prefetch" href="/assets/js/182.425fd44a.js"><link rel="prefetch" href="/assets/js/183.643e0376.js"><link rel="prefetch" href="/assets/js/184.28243fe4.js"><link rel="prefetch" href="/assets/js/185.145fafb0.js"><link rel="prefetch" href="/assets/js/186.9c005fb8.js"><link rel="prefetch" href="/assets/js/187.a1c8a8da.js"><link rel="prefetch" href="/assets/js/188.b78deff0.js"><link rel="prefetch" href="/assets/js/189.86432945.js"><link rel="prefetch" href="/assets/js/19.992da7e4.js"><link rel="prefetch" href="/assets/js/190.b6c616c9.js"><link rel="prefetch" href="/assets/js/191.d2a4a045.js"><link rel="prefetch" href="/assets/js/192.ce93c157.js"><link rel="prefetch" href="/assets/js/193.f45b56e8.js"><link rel="prefetch" href="/assets/js/194.60166b01.js"><link rel="prefetch" href="/assets/js/195.fea0fdcc.js"><link rel="prefetch" href="/assets/js/196.7f9353e4.js"><link rel="prefetch" href="/assets/js/197.2a8de731.js"><link rel="prefetch" href="/assets/js/198.6f3d807b.js"><link rel="prefetch" href="/assets/js/199.75028922.js"><link rel="prefetch" href="/assets/js/20.e27836ed.js"><link rel="prefetch" href="/assets/js/200.36fbe8e0.js"><link rel="prefetch" href="/assets/js/201.ca3a3d7d.js"><link rel="prefetch" href="/assets/js/202.8cc508cd.js"><link rel="prefetch" href="/assets/js/203.eb6662a4.js"><link rel="prefetch" href="/assets/js/204.a75edc0d.js"><link rel="prefetch" href="/assets/js/205.77cc7661.js"><link rel="prefetch" href="/assets/js/206.7cfc88ae.js"><link rel="prefetch" href="/assets/js/207.9d5b5377.js"><link rel="prefetch" href="/assets/js/208.9308a3b3.js"><link rel="prefetch" href="/assets/js/209.cbee10e7.js"><link rel="prefetch" href="/assets/js/21.9bc4424f.js"><link rel="prefetch" href="/assets/js/210.3dbd53b3.js"><link rel="prefetch" href="/assets/js/211.ffc0051e.js"><link rel="prefetch" href="/assets/js/212.420b9a23.js"><link rel="prefetch" href="/assets/js/213.da84f0aa.js"><link rel="prefetch" href="/assets/js/214.2a5308ff.js"><link rel="prefetch" href="/assets/js/215.bc87143e.js"><link rel="prefetch" href="/assets/js/216.f099b04d.js"><link rel="prefetch" href="/assets/js/217.39cc059e.js"><link rel="prefetch" href="/assets/js/218.3b588871.js"><link rel="prefetch" href="/assets/js/219.8c7c7f40.js"><link rel="prefetch" href="/assets/js/22.287b20ef.js"><link rel="prefetch" href="/assets/js/220.6a490188.js"><link rel="prefetch" href="/assets/js/221.a06fe7b9.js"><link rel="prefetch" href="/assets/js/222.0da34a82.js"><link rel="prefetch" href="/assets/js/223.6d6abad9.js"><link rel="prefetch" href="/assets/js/224.de157359.js"><link rel="prefetch" href="/assets/js/225.c733d3d1.js"><link rel="prefetch" href="/assets/js/226.039d453b.js"><link rel="prefetch" href="/assets/js/227.dbe84815.js"><link rel="prefetch" href="/assets/js/228.4850e3f3.js"><link rel="prefetch" href="/assets/js/229.322215a9.js"><link rel="prefetch" href="/assets/js/23.c1fc6d56.js"><link rel="prefetch" href="/assets/js/230.2469fb45.js"><link rel="prefetch" href="/assets/js/231.a77224ae.js"><link rel="prefetch" href="/assets/js/232.56534eb1.js"><link rel="prefetch" href="/assets/js/233.f69b682d.js"><link rel="prefetch" href="/assets/js/234.33fecaf9.js"><link rel="prefetch" href="/assets/js/235.3152a6d8.js"><link rel="prefetch" href="/assets/js/236.4a45a619.js"><link rel="prefetch" href="/assets/js/237.683796c5.js"><link rel="prefetch" href="/assets/js/238.4183baab.js"><link rel="prefetch" href="/assets/js/239.967342f3.js"><link rel="prefetch" href="/assets/js/24.c4266153.js"><link rel="prefetch" href="/assets/js/240.4ebdaa3e.js"><link rel="prefetch" href="/assets/js/241.3853f81e.js"><link rel="prefetch" href="/assets/js/242.0be00241.js"><link rel="prefetch" href="/assets/js/243.27a16565.js"><link rel="prefetch" href="/assets/js/244.4b6c0842.js"><link rel="prefetch" href="/assets/js/245.0ff5b09e.js"><link rel="prefetch" href="/assets/js/246.ec9708bc.js"><link rel="prefetch" href="/assets/js/247.33dd2e3f.js"><link rel="prefetch" href="/assets/js/248.e095c83d.js"><link rel="prefetch" href="/assets/js/249.e35dae0b.js"><link rel="prefetch" href="/assets/js/25.0bd19957.js"><link rel="prefetch" href="/assets/js/250.b7dda30b.js"><link rel="prefetch" href="/assets/js/251.373c219f.js"><link rel="prefetch" href="/assets/js/252.f02d8652.js"><link rel="prefetch" href="/assets/js/253.0129ab3b.js"><link rel="prefetch" href="/assets/js/254.05bc87ae.js"><link rel="prefetch" href="/assets/js/255.93959060.js"><link rel="prefetch" href="/assets/js/256.036268bb.js"><link rel="prefetch" href="/assets/js/257.4cfe4c46.js"><link rel="prefetch" href="/assets/js/258.70f49e1e.js"><link rel="prefetch" href="/assets/js/259.e92d7a7e.js"><link rel="prefetch" href="/assets/js/26.cd8cc5bc.js"><link rel="prefetch" href="/assets/js/260.24ecb139.js"><link rel="prefetch" href="/assets/js/261.32f0c433.js"><link rel="prefetch" href="/assets/js/262.aca4b5e9.js"><link rel="prefetch" href="/assets/js/263.0051554a.js"><link rel="prefetch" href="/assets/js/264.063d3092.js"><link rel="prefetch" href="/assets/js/265.de1fe60c.js"><link rel="prefetch" href="/assets/js/266.4407a594.js"><link rel="prefetch" href="/assets/js/267.9318dca9.js"><link rel="prefetch" href="/assets/js/268.b9696b4c.js"><link rel="prefetch" href="/assets/js/269.21743bc6.js"><link rel="prefetch" href="/assets/js/27.e0c9a2d1.js"><link rel="prefetch" href="/assets/js/270.64175904.js"><link rel="prefetch" href="/assets/js/271.ab988e51.js"><link rel="prefetch" href="/assets/js/272.40190656.js"><link rel="prefetch" href="/assets/js/273.124f97d6.js"><link rel="prefetch" href="/assets/js/274.ac2ae949.js"><link rel="prefetch" href="/assets/js/275.84112c31.js"><link rel="prefetch" href="/assets/js/276.5cd3a2f1.js"><link rel="prefetch" href="/assets/js/277.dfd266d2.js"><link rel="prefetch" href="/assets/js/278.2c22b507.js"><link rel="prefetch" href="/assets/js/279.143630b9.js"><link rel="prefetch" href="/assets/js/28.ee8b098b.js"><link rel="prefetch" href="/assets/js/280.e52e72d5.js"><link rel="prefetch" href="/assets/js/281.fa255716.js"><link rel="prefetch" href="/assets/js/282.33cf3680.js"><link rel="prefetch" href="/assets/js/283.8aaeb880.js"><link rel="prefetch" href="/assets/js/284.cce2c80c.js"><link rel="prefetch" href="/assets/js/285.649e1ab2.js"><link rel="prefetch" href="/assets/js/286.93d1a5fb.js"><link rel="prefetch" href="/assets/js/287.95ecc60d.js"><link rel="prefetch" href="/assets/js/288.d0316c60.js"><link rel="prefetch" href="/assets/js/289.96b0da90.js"><link rel="prefetch" href="/assets/js/29.f1800df7.js"><link rel="prefetch" href="/assets/js/290.a0ec1eb0.js"><link rel="prefetch" href="/assets/js/291.000c9293.js"><link rel="prefetch" href="/assets/js/292.aa442a45.js"><link rel="prefetch" href="/assets/js/293.ad41a62d.js"><link rel="prefetch" href="/assets/js/294.d01fa093.js"><link rel="prefetch" href="/assets/js/295.988cbaa2.js"><link rel="prefetch" href="/assets/js/296.b4376d7c.js"><link rel="prefetch" href="/assets/js/297.53d3839b.js"><link rel="prefetch" href="/assets/js/298.e41d3af5.js"><link rel="prefetch" href="/assets/js/299.7530e3f7.js"><link rel="prefetch" href="/assets/js/3.0318d431.js"><link rel="prefetch" href="/assets/js/30.e022632d.js"><link rel="prefetch" href="/assets/js/300.b89cf9f0.js"><link rel="prefetch" href="/assets/js/301.538c5d13.js"><link rel="prefetch" href="/assets/js/302.e61e98d4.js"><link rel="prefetch" href="/assets/js/303.e69fdf1f.js"><link rel="prefetch" href="/assets/js/304.12cf05d2.js"><link rel="prefetch" href="/assets/js/305.05630898.js"><link rel="prefetch" href="/assets/js/306.4423e4cb.js"><link rel="prefetch" href="/assets/js/307.ec499705.js"><link rel="prefetch" href="/assets/js/308.eae04a19.js"><link rel="prefetch" href="/assets/js/309.e8cdb29d.js"><link rel="prefetch" href="/assets/js/31.a2dfbc5f.js"><link rel="prefetch" href="/assets/js/310.3770a9fc.js"><link rel="prefetch" href="/assets/js/311.79ae7adb.js"><link rel="prefetch" href="/assets/js/312.fd3baefc.js"><link rel="prefetch" href="/assets/js/313.895f6dcd.js"><link rel="prefetch" href="/assets/js/314.85943d2f.js"><link rel="prefetch" href="/assets/js/315.69631810.js"><link rel="prefetch" href="/assets/js/316.b025621c.js"><link rel="prefetch" href="/assets/js/317.7b7974aa.js"><link rel="prefetch" href="/assets/js/318.972a129d.js"><link rel="prefetch" href="/assets/js/319.65a4d2cf.js"><link rel="prefetch" href="/assets/js/32.b143e718.js"><link rel="prefetch" href="/assets/js/320.e5635579.js"><link rel="prefetch" href="/assets/js/321.845573fa.js"><link rel="prefetch" href="/assets/js/322.0f95ad9a.js"><link rel="prefetch" href="/assets/js/323.f7d22184.js"><link rel="prefetch" href="/assets/js/324.eb027f24.js"><link rel="prefetch" href="/assets/js/325.f54af6ec.js"><link rel="prefetch" href="/assets/js/326.7a921d9f.js"><link rel="prefetch" href="/assets/js/327.e9c43c17.js"><link rel="prefetch" href="/assets/js/328.586efc33.js"><link rel="prefetch" href="/assets/js/329.47017c3f.js"><link rel="prefetch" href="/assets/js/33.e17e09ac.js"><link rel="prefetch" href="/assets/js/330.81032fbd.js"><link rel="prefetch" href="/assets/js/331.ce9966db.js"><link rel="prefetch" href="/assets/js/332.c28e794e.js"><link rel="prefetch" href="/assets/js/333.4564d08a.js"><link rel="prefetch" href="/assets/js/334.3b421837.js"><link rel="prefetch" href="/assets/js/335.b2b74b9d.js"><link rel="prefetch" href="/assets/js/336.9dd1e510.js"><link rel="prefetch" href="/assets/js/337.03042431.js"><link rel="prefetch" href="/assets/js/338.1bc0b80f.js"><link rel="prefetch" href="/assets/js/339.e517fc5c.js"><link rel="prefetch" href="/assets/js/34.f287ac3d.js"><link rel="prefetch" href="/assets/js/340.f90d2df3.js"><link rel="prefetch" href="/assets/js/341.eccb4ec1.js"><link rel="prefetch" href="/assets/js/342.b3386439.js"><link rel="prefetch" href="/assets/js/343.2ee6901d.js"><link rel="prefetch" href="/assets/js/344.e6913fc7.js"><link rel="prefetch" href="/assets/js/345.a72760e7.js"><link rel="prefetch" href="/assets/js/346.13984d25.js"><link rel="prefetch" href="/assets/js/347.6b59cbaf.js"><link rel="prefetch" href="/assets/js/348.f43d5e47.js"><link rel="prefetch" href="/assets/js/349.fe8641cf.js"><link rel="prefetch" href="/assets/js/35.5a1dace7.js"><link rel="prefetch" href="/assets/js/350.0ceb9652.js"><link rel="prefetch" href="/assets/js/351.08e70696.js"><link rel="prefetch" href="/assets/js/352.958f535b.js"><link rel="prefetch" href="/assets/js/353.51463d78.js"><link rel="prefetch" href="/assets/js/354.6169e165.js"><link rel="prefetch" href="/assets/js/355.10447463.js"><link rel="prefetch" href="/assets/js/356.32983151.js"><link rel="prefetch" href="/assets/js/357.39e998b6.js"><link rel="prefetch" href="/assets/js/358.1f40aee7.js"><link rel="prefetch" href="/assets/js/359.d1e82e86.js"><link rel="prefetch" href="/assets/js/36.b6f4332a.js"><link rel="prefetch" href="/assets/js/360.9096bf48.js"><link rel="prefetch" href="/assets/js/361.e2c0815a.js"><link rel="prefetch" href="/assets/js/362.66983024.js"><link rel="prefetch" href="/assets/js/363.d7f0691d.js"><link rel="prefetch" href="/assets/js/364.d96ddc65.js"><link rel="prefetch" href="/assets/js/365.c92ad624.js"><link rel="prefetch" href="/assets/js/366.dfd66280.js"><link rel="prefetch" href="/assets/js/367.01503521.js"><link rel="prefetch" href="/assets/js/368.8d83b9c1.js"><link rel="prefetch" href="/assets/js/369.f8e08a4f.js"><link rel="prefetch" href="/assets/js/37.f1a16008.js"><link rel="prefetch" href="/assets/js/370.70b912f3.js"><link rel="prefetch" href="/assets/js/371.dcefb388.js"><link rel="prefetch" href="/assets/js/372.a81a499a.js"><link rel="prefetch" href="/assets/js/373.94458b0f.js"><link rel="prefetch" href="/assets/js/374.a406f06f.js"><link rel="prefetch" href="/assets/js/375.87287c02.js"><link rel="prefetch" href="/assets/js/376.26088425.js"><link rel="prefetch" href="/assets/js/377.b9ee096c.js"><link rel="prefetch" href="/assets/js/378.7a1b6fa7.js"><link rel="prefetch" href="/assets/js/379.3e2b62fc.js"><link rel="prefetch" href="/assets/js/38.59f5160c.js"><link rel="prefetch" href="/assets/js/380.d741385f.js"><link rel="prefetch" href="/assets/js/381.afc0104a.js"><link rel="prefetch" href="/assets/js/382.a8c02915.js"><link rel="prefetch" href="/assets/js/383.7fca9756.js"><link rel="prefetch" href="/assets/js/384.d08aa931.js"><link rel="prefetch" href="/assets/js/385.c3ab471f.js"><link rel="prefetch" href="/assets/js/386.7314b80e.js"><link rel="prefetch" href="/assets/js/387.8db3a14a.js"><link rel="prefetch" href="/assets/js/388.f618a3b3.js"><link rel="prefetch" href="/assets/js/389.4d35947d.js"><link rel="prefetch" href="/assets/js/39.3cf9af40.js"><link rel="prefetch" href="/assets/js/390.a8e04e41.js"><link rel="prefetch" href="/assets/js/391.a31e9a62.js"><link rel="prefetch" href="/assets/js/392.d9321e46.js"><link rel="prefetch" href="/assets/js/393.6c4834d0.js"><link rel="prefetch" href="/assets/js/394.fd0a0ea4.js"><link rel="prefetch" href="/assets/js/395.0f27ab48.js"><link rel="prefetch" href="/assets/js/396.70044e25.js"><link rel="prefetch" href="/assets/js/397.07b2c0a6.js"><link rel="prefetch" href="/assets/js/398.ba95a9c5.js"><link rel="prefetch" href="/assets/js/399.8b310fbc.js"><link rel="prefetch" href="/assets/js/4.45f61616.js"><link rel="prefetch" href="/assets/js/40.fcf089d7.js"><link rel="prefetch" href="/assets/js/400.7ff77c6c.js"><link rel="prefetch" href="/assets/js/401.840e0c7c.js"><link rel="prefetch" href="/assets/js/402.a722c16f.js"><link rel="prefetch" href="/assets/js/403.1a3c12fb.js"><link rel="prefetch" href="/assets/js/404.7da4d4a4.js"><link rel="prefetch" href="/assets/js/405.76a07310.js"><link rel="prefetch" href="/assets/js/406.176db1fd.js"><link rel="prefetch" href="/assets/js/407.ff3da33f.js"><link rel="prefetch" href="/assets/js/408.3b4dfb3a.js"><link rel="prefetch" href="/assets/js/409.05692a2e.js"><link rel="prefetch" href="/assets/js/41.3f0a746d.js"><link rel="prefetch" href="/assets/js/410.615dc40b.js"><link rel="prefetch" href="/assets/js/411.e542a59f.js"><link rel="prefetch" href="/assets/js/412.16fc0c97.js"><link rel="prefetch" href="/assets/js/413.b9f30c37.js"><link rel="prefetch" href="/assets/js/414.9629300e.js"><link rel="prefetch" href="/assets/js/415.5c12951e.js"><link rel="prefetch" href="/assets/js/416.3ede10bc.js"><link rel="prefetch" href="/assets/js/417.5bc08adb.js"><link rel="prefetch" href="/assets/js/418.0a54fe32.js"><link rel="prefetch" href="/assets/js/419.97ebd724.js"><link rel="prefetch" href="/assets/js/42.d0fdcdd4.js"><link rel="prefetch" href="/assets/js/420.d3f60a7a.js"><link rel="prefetch" href="/assets/js/421.6b187cc9.js"><link rel="prefetch" href="/assets/js/422.268b38aa.js"><link rel="prefetch" href="/assets/js/423.00f151fe.js"><link rel="prefetch" href="/assets/js/424.5d54e48d.js"><link rel="prefetch" href="/assets/js/425.b0e71df6.js"><link rel="prefetch" href="/assets/js/426.fb5d6c08.js"><link rel="prefetch" href="/assets/js/427.a7a42bdb.js"><link rel="prefetch" href="/assets/js/428.b41b80fb.js"><link rel="prefetch" href="/assets/js/429.aff3b223.js"><link rel="prefetch" href="/assets/js/43.7812871c.js"><link rel="prefetch" href="/assets/js/430.9bded6a2.js"><link rel="prefetch" href="/assets/js/431.fbd064dd.js"><link rel="prefetch" href="/assets/js/432.a0ccaf13.js"><link rel="prefetch" href="/assets/js/433.70729631.js"><link rel="prefetch" href="/assets/js/434.7ff21dc4.js"><link rel="prefetch" href="/assets/js/435.ba6f0c33.js"><link rel="prefetch" href="/assets/js/436.abcca44e.js"><link rel="prefetch" href="/assets/js/437.2b2333cb.js"><link rel="prefetch" href="/assets/js/438.93ea3d14.js"><link rel="prefetch" href="/assets/js/439.c1b946ea.js"><link rel="prefetch" href="/assets/js/44.d2bbbf62.js"><link rel="prefetch" href="/assets/js/440.a5c5071e.js"><link rel="prefetch" href="/assets/js/441.bad7a6f2.js"><link rel="prefetch" href="/assets/js/442.97a45e71.js"><link rel="prefetch" href="/assets/js/443.9dd7a744.js"><link rel="prefetch" href="/assets/js/444.b2e74ec9.js"><link rel="prefetch" href="/assets/js/445.181b11ad.js"><link rel="prefetch" href="/assets/js/446.1d43ea57.js"><link rel="prefetch" href="/assets/js/447.a75ca861.js"><link rel="prefetch" href="/assets/js/448.7e177e61.js"><link rel="prefetch" href="/assets/js/449.0e124a1f.js"><link rel="prefetch" href="/assets/js/45.2181b5c6.js"><link rel="prefetch" href="/assets/js/450.d18c5137.js"><link rel="prefetch" href="/assets/js/451.0296f837.js"><link rel="prefetch" href="/assets/js/452.1f5d56a5.js"><link rel="prefetch" href="/assets/js/453.6f67fa9b.js"><link rel="prefetch" href="/assets/js/454.d96cd4e8.js"><link rel="prefetch" href="/assets/js/455.488f2e23.js"><link rel="prefetch" href="/assets/js/456.264d0da2.js"><link rel="prefetch" href="/assets/js/457.329d4d26.js"><link rel="prefetch" href="/assets/js/458.d20d34f9.js"><link rel="prefetch" href="/assets/js/459.dd4fad09.js"><link rel="prefetch" href="/assets/js/46.d69710e9.js"><link rel="prefetch" href="/assets/js/460.e1f8580c.js"><link rel="prefetch" href="/assets/js/461.d47e1ab7.js"><link rel="prefetch" href="/assets/js/462.54b49f34.js"><link rel="prefetch" href="/assets/js/463.2d1bb289.js"><link rel="prefetch" href="/assets/js/464.28d2b2fe.js"><link rel="prefetch" href="/assets/js/465.474d09dd.js"><link rel="prefetch" href="/assets/js/466.3d79bf1d.js"><link rel="prefetch" href="/assets/js/467.0e38992e.js"><link rel="prefetch" href="/assets/js/468.23f8dbdb.js"><link rel="prefetch" href="/assets/js/469.424ab64e.js"><link rel="prefetch" href="/assets/js/47.fa77c18f.js"><link rel="prefetch" href="/assets/js/470.8e15adc4.js"><link rel="prefetch" href="/assets/js/471.e478b277.js"><link rel="prefetch" href="/assets/js/472.75eed247.js"><link rel="prefetch" href="/assets/js/473.676ac02f.js"><link rel="prefetch" href="/assets/js/474.ec676f10.js"><link rel="prefetch" href="/assets/js/475.0b3a7bb3.js"><link rel="prefetch" href="/assets/js/476.1dccc2bf.js"><link rel="prefetch" href="/assets/js/477.19774d6a.js"><link rel="prefetch" href="/assets/js/478.562bcdfb.js"><link rel="prefetch" href="/assets/js/479.0fdf39e1.js"><link rel="prefetch" href="/assets/js/48.55ba7067.js"><link rel="prefetch" href="/assets/js/480.32cb0959.js"><link rel="prefetch" href="/assets/js/481.39744803.js"><link rel="prefetch" href="/assets/js/482.82ff750c.js"><link rel="prefetch" href="/assets/js/483.59be5f3b.js"><link rel="prefetch" href="/assets/js/484.b47730ba.js"><link rel="prefetch" href="/assets/js/485.514e284f.js"><link rel="prefetch" href="/assets/js/486.8d407228.js"><link rel="prefetch" href="/assets/js/487.623afb9a.js"><link rel="prefetch" href="/assets/js/488.d575377d.js"><link rel="prefetch" href="/assets/js/49.369b2ef4.js"><link rel="prefetch" href="/assets/js/5.89e027e6.js"><link rel="prefetch" href="/assets/js/50.32e51808.js"><link rel="prefetch" href="/assets/js/51.48af1f55.js"><link rel="prefetch" href="/assets/js/52.0ff3366f.js"><link rel="prefetch" href="/assets/js/53.f663d530.js"><link rel="prefetch" href="/assets/js/54.57eabb55.js"><link rel="prefetch" href="/assets/js/55.00e0bdd0.js"><link rel="prefetch" href="/assets/js/56.b638bc9a.js"><link rel="prefetch" href="/assets/js/57.68420705.js"><link rel="prefetch" href="/assets/js/58.f0a325a2.js"><link rel="prefetch" href="/assets/js/59.30debc93.js"><link rel="prefetch" href="/assets/js/60.48490f44.js"><link rel="prefetch" href="/assets/js/61.26a984a9.js"><link rel="prefetch" href="/assets/js/62.f0add27d.js"><link rel="prefetch" href="/assets/js/63.07c42d31.js"><link rel="prefetch" href="/assets/js/65.c159a057.js"><link rel="prefetch" href="/assets/js/66.80e96020.js"><link rel="prefetch" href="/assets/js/67.42eabf7d.js"><link rel="prefetch" href="/assets/js/68.2a7e9954.js"><link rel="prefetch" href="/assets/js/69.4579e421.js"><link rel="prefetch" href="/assets/js/7.037ecfb1.js"><link rel="prefetch" href="/assets/js/70.4e7b95d4.js"><link rel="prefetch" href="/assets/js/71.5df75825.js"><link rel="prefetch" href="/assets/js/72.6239ec2a.js"><link rel="prefetch" href="/assets/js/73.c2458335.js"><link rel="prefetch" href="/assets/js/74.b86599e1.js"><link rel="prefetch" href="/assets/js/75.8d14cab7.js"><link rel="prefetch" href="/assets/js/76.82bf4b00.js"><link rel="prefetch" href="/assets/js/77.f5a890cc.js"><link rel="prefetch" href="/assets/js/78.f3c574f3.js"><link rel="prefetch" href="/assets/js/79.c9c56bf3.js"><link rel="prefetch" href="/assets/js/8.03d32196.js"><link rel="prefetch" href="/assets/js/80.24c4483b.js"><link rel="prefetch" href="/assets/js/81.e6653250.js"><link rel="prefetch" href="/assets/js/82.0da4ae5d.js"><link rel="prefetch" href="/assets/js/83.89a8c965.js"><link rel="prefetch" href="/assets/js/84.56206c88.js"><link rel="prefetch" href="/assets/js/85.0daf7cf7.js"><link rel="prefetch" href="/assets/js/86.0a17b684.js"><link rel="prefetch" href="/assets/js/87.f7cf9412.js"><link rel="prefetch" href="/assets/js/88.22341e3f.js"><link rel="prefetch" href="/assets/js/89.2166c8bb.js"><link rel="prefetch" href="/assets/js/9.a241a058.js"><link rel="prefetch" href="/assets/js/90.9440815d.js"><link rel="prefetch" href="/assets/js/91.5ea69e27.js"><link rel="prefetch" href="/assets/js/92.cea1c8dd.js"><link rel="prefetch" href="/assets/js/93.2e94ab93.js"><link rel="prefetch" href="/assets/js/94.1674ba0c.js"><link rel="prefetch" href="/assets/js/95.c6ba057e.js"><link rel="prefetch" href="/assets/js/96.ee719565.js"><link rel="prefetch" href="/assets/js/97.a814f163.js"><link rel="prefetch" href="/assets/js/98.748b1098.js"><link rel="prefetch" href="/assets/js/99.c6176c0d.js">
    <link rel="stylesheet" href="/assets/css/0.styles.e57fdc06.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><img src="/logo.png" alt="房飞跃的博客" class="logo"> <span class="site-name can-hide">房飞跃的博客</span></a> <div class="links"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="前端" class="dropdown-title"><span class="title">前端</span> <span class="arrow down"></span></button> <button type="button" aria-label="前端" class="mobile-dropdown-title"><span class="title">前端</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>
          Vue
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/books/深入浅出Vue.js/01.html" class="nav-link">
  深入浅出Vue
</a></li><li class="dropdown-subitem"><a href="/front/vue/vue/01.html" class="nav-link">
  Vue
</a></li><li class="dropdown-subitem"><a href="/front/vue/vue-router/01.html" class="nav-link">
  VueRouter
</a></li><li class="dropdown-subitem"><a href="/front/vue/Vuex/01.html" class="nav-link">
  Vuex
</a></li><li class="dropdown-subitem"><a href="/front/vue/vue3/01.html" class="nav-link">
  Vue3核心剖析
</a></li><li class="dropdown-subitem"><a href="/front/vue/Vue知识点简单梳理/01.html" class="nav-link">
  Vue知识点简单梳理
</a></li></ul></li><li class="dropdown-item"><h4>
          React
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/books/深入React技术栈/01.html" class="nav-link">
  深入React技术栈
</a></li><li class="dropdown-subitem"><a href="/front/react/React进阶实践指南/01.html" class="nav-link">
  React进阶实践指南
</a></li><li class="dropdown-subitem"><a href="/front/react/React知识点简单梳理/01.html" class="nav-link">
  React知识点简单梳理
</a></li></ul></li><li class="dropdown-item"><h4>
          混合开发
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/front/混合开发/01.html" class="nav-link">
  混合开发探究
</a></li></ul></li><li class="dropdown-item"><h4>
          TypeScript
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/front/ts/极简入门Typescript/01.html" class="nav-link">
  极简入门Typescript
</a></li></ul></li><li class="dropdown-item"><h4>
          Webpack
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/front/webpack/极简入门webpack/01.html" class="nav-link">
  极简入门
</a></li><li class="dropdown-subitem"><a href="/front/webpack/常见面试题/01.html" class="nav-link">
  常见面试题
</a></li></ul></li><li class="dropdown-item"><h4>
          设计模式
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/front/设计模式/JS设计模式核心原理和应用实践/01.html" class="nav-link">
  JS设计模式核心原理和应用实践
</a></li></ul></li><li class="dropdown-item"><h4>
          算法和数据结构
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/front/算法和数据结构/入门级算法/01.html" class="nav-link">
  入门级算法
</a></li><li class="dropdown-subitem"><a href="/front/算法和数据结构/常见算法/01.html" class="nav-link">
  常见算法
</a></li><li class="dropdown-subitem"><a href="/front/算法和数据结构/常见数据结构/01.html" class="nav-link">
  常见数据结构
</a></li><li class="dropdown-subitem"><a href="/front/算法和数据结构/前端算法与数据结构/01.html" class="nav-link">
  前端算法与数据结构
</a></li></ul></li><li class="dropdown-item"><h4>
          基础必备
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/front/base/html必备/01.html" class="nav-link">
  HTML必备
</a></li><li class="dropdown-subitem"><a href="/front/base/CSS必备/01.html" class="nav-link">
  CSS必备
</a></li><li class="dropdown-subitem"><a href="/front/base/JS基础/01.html" class="nav-link">
  JS基础
</a></li><li class="dropdown-subitem"><a href="/front/base/JS进阶/01.html" class="nav-link">
  JS进阶
</a></li><li class="dropdown-subitem"><a href="/front/base/JS练习/01.html" class="nav-link">
  JS练习
</a></li><li class="dropdown-subitem"><a href="/front/base/网络基础/01.html" class="nav-link">
  网络基础
</a></li><li class="dropdown-subitem"><a href="/books/JS高级程序设计/01.html" class="nav-link">
  JS高级程序设计
</a></li><li class="dropdown-subitem"><a href="/front/base/浏览器相关基础/01.html" class="nav-link">
  浏览器相关基础
</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="电子" class="dropdown-title"><span class="title">电子</span> <span class="arrow down"></span></button> <button type="button" aria-label="电子" class="mobile-dropdown-title"><span class="title">电子</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>
          STM32
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/电子/STM32四轴飞行器/01.html" class="nav-link">
  STM32四轴飞行器
</a></li></ul></li><li class="dropdown-item"><h4>
          Arduino
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/电子/Arduino墙画机/01.html" class="nav-link">
  Arduino墙画机
</a></li><li class="dropdown-subitem"><a href="/电子/Arduino四轴飞行器/01.html" class="nav-link">
  Arduino四轴飞行器
</a></li><li class="dropdown-subitem"><a href="/电子/Arduino四足仿生机器人/01.html" class="nav-link">
  Arduino四足仿生机器人
</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="关于" class="dropdown-title"><span class="title">关于</span> <span class="arrow down"></span></button> <button type="button" aria-label="关于" class="mobile-dropdown-title"><span class="title">关于</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/关于我/01.html" class="nav-link">
  关于我
</a></li><li class="dropdown-item"><!----> <a href="https://github.com/fangfeiyue" target="_blank" rel="noopener noreferrer" class="nav-link external">
  Github
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></li></ul></div></div> <!----></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><nav class="nav-links"><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="前端" class="dropdown-title"><span class="title">前端</span> <span class="arrow down"></span></button> <button type="button" aria-label="前端" class="mobile-dropdown-title"><span class="title">前端</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>
          Vue
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/books/深入浅出Vue.js/01.html" class="nav-link">
  深入浅出Vue
</a></li><li class="dropdown-subitem"><a href="/front/vue/vue/01.html" class="nav-link">
  Vue
</a></li><li class="dropdown-subitem"><a href="/front/vue/vue-router/01.html" class="nav-link">
  VueRouter
</a></li><li class="dropdown-subitem"><a href="/front/vue/Vuex/01.html" class="nav-link">
  Vuex
</a></li><li class="dropdown-subitem"><a href="/front/vue/vue3/01.html" class="nav-link">
  Vue3核心剖析
</a></li><li class="dropdown-subitem"><a href="/front/vue/Vue知识点简单梳理/01.html" class="nav-link">
  Vue知识点简单梳理
</a></li></ul></li><li class="dropdown-item"><h4>
          React
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/books/深入React技术栈/01.html" class="nav-link">
  深入React技术栈
</a></li><li class="dropdown-subitem"><a href="/front/react/React进阶实践指南/01.html" class="nav-link">
  React进阶实践指南
</a></li><li class="dropdown-subitem"><a href="/front/react/React知识点简单梳理/01.html" class="nav-link">
  React知识点简单梳理
</a></li></ul></li><li class="dropdown-item"><h4>
          混合开发
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/front/混合开发/01.html" class="nav-link">
  混合开发探究
</a></li></ul></li><li class="dropdown-item"><h4>
          TypeScript
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/front/ts/极简入门Typescript/01.html" class="nav-link">
  极简入门Typescript
</a></li></ul></li><li class="dropdown-item"><h4>
          Webpack
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/front/webpack/极简入门webpack/01.html" class="nav-link">
  极简入门
</a></li><li class="dropdown-subitem"><a href="/front/webpack/常见面试题/01.html" class="nav-link">
  常见面试题
</a></li></ul></li><li class="dropdown-item"><h4>
          设计模式
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/front/设计模式/JS设计模式核心原理和应用实践/01.html" class="nav-link">
  JS设计模式核心原理和应用实践
</a></li></ul></li><li class="dropdown-item"><h4>
          算法和数据结构
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/front/算法和数据结构/入门级算法/01.html" class="nav-link">
  入门级算法
</a></li><li class="dropdown-subitem"><a href="/front/算法和数据结构/常见算法/01.html" class="nav-link">
  常见算法
</a></li><li class="dropdown-subitem"><a href="/front/算法和数据结构/常见数据结构/01.html" class="nav-link">
  常见数据结构
</a></li><li class="dropdown-subitem"><a href="/front/算法和数据结构/前端算法与数据结构/01.html" class="nav-link">
  前端算法与数据结构
</a></li></ul></li><li class="dropdown-item"><h4>
          基础必备
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/front/base/html必备/01.html" class="nav-link">
  HTML必备
</a></li><li class="dropdown-subitem"><a href="/front/base/CSS必备/01.html" class="nav-link">
  CSS必备
</a></li><li class="dropdown-subitem"><a href="/front/base/JS基础/01.html" class="nav-link">
  JS基础
</a></li><li class="dropdown-subitem"><a href="/front/base/JS进阶/01.html" class="nav-link">
  JS进阶
</a></li><li class="dropdown-subitem"><a href="/front/base/JS练习/01.html" class="nav-link">
  JS练习
</a></li><li class="dropdown-subitem"><a href="/front/base/网络基础/01.html" class="nav-link">
  网络基础
</a></li><li class="dropdown-subitem"><a href="/books/JS高级程序设计/01.html" class="nav-link">
  JS高级程序设计
</a></li><li class="dropdown-subitem"><a href="/front/base/浏览器相关基础/01.html" class="nav-link">
  浏览器相关基础
</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="电子" class="dropdown-title"><span class="title">电子</span> <span class="arrow down"></span></button> <button type="button" aria-label="电子" class="mobile-dropdown-title"><span class="title">电子</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>
          STM32
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/电子/STM32四轴飞行器/01.html" class="nav-link">
  STM32四轴飞行器
</a></li></ul></li><li class="dropdown-item"><h4>
          Arduino
        </h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/电子/Arduino墙画机/01.html" class="nav-link">
  Arduino墙画机
</a></li><li class="dropdown-subitem"><a href="/电子/Arduino四轴飞行器/01.html" class="nav-link">
  Arduino四轴飞行器
</a></li><li class="dropdown-subitem"><a href="/电子/Arduino四足仿生机器人/01.html" class="nav-link">
  Arduino四足仿生机器人
</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="关于" class="dropdown-title"><span class="title">关于</span> <span class="arrow down"></span></button> <button type="button" aria-label="关于" class="mobile-dropdown-title"><span class="title">关于</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/关于我/01.html" class="nav-link">
  关于我
</a></li><li class="dropdown-item"><!----> <a href="https://github.com/fangfeiyue" target="_blank" rel="noopener noreferrer" class="nav-link external">
  Github
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></li></ul></div></div> <!----></nav>  <ul class="sidebar-links"><li><section class="sidebar-group depth-0"><p class="sidebar-heading open"><span>常见数据结构</span> <!----></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/front/算法和数据结构/常见数据结构/01.html" class="sidebar-link">简介</a></li><li><a href="/front/算法和数据结构/常见数据结构/02.html" class="sidebar-link">数组</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/02.html#泛型类" class="sidebar-link">泛型类</a></li><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/02.html#动态数组" class="sidebar-link">动态数组</a></li><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/02.html#复杂度分析" class="sidebar-link">复杂度分析</a></li><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/02.html#均摊时间复杂度" class="sidebar-link">均摊时间复杂度</a></li><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/02.html#复杂度震荡" class="sidebar-link">复杂度震荡</a></li></ul></li><li><a href="/front/算法和数据结构/常见数据结构/03.html" class="sidebar-link">栈</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/03.html#栈的简介" class="sidebar-link">栈的简介</a></li><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/03.html#栈的应用" class="sidebar-link">栈的应用</a></li><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/03.html#栈的基本实现" class="sidebar-link">栈的基本实现</a></li><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/03.html#复杂度分析" class="sidebar-link">复杂度分析</a></li><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/03.html#括号匹配" class="sidebar-link">括号匹配</a></li></ul></li><li><a href="/front/算法和数据结构/常见数据结构/04.html" class="sidebar-link">队列</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/04.html#队列简介" class="sidebar-link">队列简介</a></li><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/04.html#队列的基本实现" class="sidebar-link">队列的基本实现</a></li><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/04.html#复杂度分析" class="sidebar-link">复杂度分析</a></li><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/04.html#循环队列" class="sidebar-link">循环队列</a></li><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/04.html#复杂度分析-2" class="sidebar-link">复杂度分析</a></li><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/04.html#数组队列和循环队列的比较" class="sidebar-link">数组队列和循环队列的比较</a></li><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/04.html#双端队列" class="sidebar-link">双端队列</a></li><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/04.html#练习" class="sidebar-link">练习</a></li></ul></li><li><a href="/front/算法和数据结构/常见数据结构/05.html" class="active sidebar-link">链表</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/05.html#链表简介" class="sidebar-link">链表简介</a></li><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/05.html#数组和链表的对比" class="sidebar-link">数组和链表的对比</a></li><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/05.html#链表的简单实现" class="sidebar-link">链表的简单实现</a></li><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/05.html#链表虚拟头节点" class="sidebar-link">链表虚拟头节点</a></li><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/05.html#链表的遍历、查询和修改" class="sidebar-link">链表的遍历、查询和修改</a></li><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/05.html#从链表中删除元素" class="sidebar-link">从链表中删除元素</a></li><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/05.html#使用链表实现栈" class="sidebar-link">使用链表实现栈</a></li><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/05.html#使用链表实现队列" class="sidebar-link">使用链表实现队列</a></li><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/05.html#链表真题练习" class="sidebar-link">链表真题练习</a></li><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/05.html#链表和递归" class="sidebar-link">链表和递归</a></li><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/05.html#递归再深入" class="sidebar-link">递归再深入</a></li><li class="sidebar-sub-header"><a href="/front/算法和数据结构/常见数据结构/05.html#翻转链表" class="sidebar-link">翻转链表</a></li></ul></li></ul></section></li></ul> </aside> <main class="page"> <div class="theme-default-content content__default"><h2 id="链表简介"><a href="#链表简介" class="header-anchor">#</a> 链表简介</h2> <p>前面我们分别介绍了三种线性数据结构，分别是动态数组、栈、队列。底层都是依托静态数组，靠resize解决固定容量问题。下面我们简单来介绍下链表这种数据结构。</p> <p>链表是一种真正的动态数据结构，也是最简单的动态数据结构，学好链表可以帮我们更好的学习后面的二分搜索树、平衡二叉树、红黑树、AVL树等动态数据结构。链表可以帮我们更深入的理解引用（或者指针），链表有着非常清晰的递归结构，可以帮助我们更加深入的理解递归。链表还可以辅助组成其他数据结构，如哈希表等。</p> <p>链表中的数据存储在节点中，通过next指向下一个数据。
<img src="" alt=""></p> <p>链表的优点：链表是真正的动态数据结构，不需要处理固定容量的问题，对于链表来说，需要存储多少数据，生成对应的节点，把它们挂接起来就行</p> <p>链表的缺点：丧失了随机访问的能力，不能像数组一样通过索引直接拿到对应的元素。这是因为数组所开辟的空间在内存中是连续分布的，可以直接通过这个索引对应的偏移直接计算出这个数据所存储的内存地址，直接用O(1)的复杂度就能把数据取出。但是链表不同，链表是靠next一层一层链接的，在计算机的底层每个节点所在的内存的位置是不同的，必须靠next一个一个的找到要找的元素。</p> <p>链表中的数据在内存中是散落分布的：
<img src="" alt=""></p> <h2 id="数组和链表的对比"><a href="#数组和链表的对比" class="header-anchor">#</a> 数组和链表的对比</h2> <p>数组最好用于索引有语义的情况，最大的优点支持快速查询。链表不适合用于索引有语义的情况，最大的有点是动态。</p> <h2 id="链表的简单实现"><a href="#链表的简单实现" class="header-anchor">#</a> 链表的简单实现</h2> <p>链表是由一个一个节点组成的，每个节点包含两个属性，分别是值和指向下一个元素的next引用。因为节点是属于链表的，所以我们设计两个类，分别为LinkedList和Node。</p> <div class="language-java extra-class"><pre class="language-java"><code><span class="token keyword">public</span> <span class="token keyword">class</span> <span class="token class-name">LinkedList</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">E</span><span class="token punctuation">&gt;</span></span> <span class="token punctuation">{</span>
  <span class="token keyword">private</span> <span class="token keyword">class</span> <span class="token class-name">Node</span><span class="token punctuation">{</span>
    <span class="token keyword">public</span> <span class="token class-name">E</span> e<span class="token punctuation">;</span>
    <span class="token keyword">public</span> <span class="token class-name">Node</span> next<span class="token punctuation">;</span>

    <span class="token keyword">public</span> <span class="token class-name">Node</span><span class="token punctuation">(</span><span class="token class-name">E</span> e<span class="token punctuation">,</span> <span class="token class-name">Node</span> next<span class="token punctuation">)</span><span class="token punctuation">{</span>
      <span class="token keyword">this</span><span class="token punctuation">.</span>e <span class="token operator">=</span> e<span class="token punctuation">;</span>
      <span class="token keyword">this</span><span class="token punctuation">.</span>next <span class="token operator">=</span> next<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">public</span> <span class="token class-name">Node</span><span class="token punctuation">(</span><span class="token class-name">E</span> e<span class="token punctuation">)</span><span class="token punctuation">{</span>
      <span class="token keyword">this</span><span class="token punctuation">(</span>e<span class="token punctuation">,</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">public</span> <span class="token class-name">Node</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
      <span class="token keyword">this</span><span class="token punctuation">(</span><span class="token keyword">null</span><span class="token punctuation">,</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 方便后续的打印输出</span>
    <span class="token annotation punctuation">@Override</span>
    <span class="token keyword">public</span> <span class="token class-name">String</span> <span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
      <span class="token keyword">return</span> e<span class="token punctuation">.</span><span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
  <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><p>上面我们简单实现了组成链表的节点类，下面我们来实现链表中的一些常用方法。</p> <p>我们要想访问链表中所有的节点，就需要把链表的头存储起来，通常链表的头叫head，所以我们需要声明一个节点head，除此之外我们还需要记录链表中存储的节点个数。</p> <div class="language-java extra-class"><pre class="language-java"><code><span class="token comment">// head节点</span>
<span class="token keyword">private</span> <span class="token class-name">Node</span> head<span class="token punctuation">;</span>
<span class="token comment">// 存储链表中节点个数</span>
<span class="token keyword">private</span> <span class="token keyword">int</span> size<span class="token punctuation">;</span>
</code></pre></div><p>获取链表中的元素个数和判断链表是否为空比较简单，这里直接给出</p> <div class="language-java extra-class"><pre class="language-java"><code><span class="token comment">// 获取链表中的元素个数</span>
<span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">getSize</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
  <span class="token keyword">return</span> size<span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token comment">// 返回链表是否为空</span>
<span class="token keyword">public</span> <span class="token keyword">boolean</span> <span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
    <span class="token keyword">return</span> size <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre></div><h3 id="在链表头部插入节点"><a href="#在链表头部插入节点" class="header-anchor">#</a> 在链表头部插入节点</h3> <p>下面我们来实现给链表添加节点的功能，给链表添加节点分为在链表头部添加节点和在链表中间添加节点。对于数组来说在数组尾部添加元素是很简单的，但对于链表来说却是给链表头部添加节点更简单。因为对于链表我们有个head变量在记录链表的头，但没有变量记录链表的尾部。</p> <p>如图，如果我们想把节点0插入到链表的头部，只需要将节点0的next指向节点head，并将节点0赋值给head即可。
<img src="/assets/img/4.3e6ad786.png" alt=""></p> <div class="language-java extra-class"><pre class="language-java"><code><span class="token comment">// 在链表头添加新的元素e</span>
<span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">addFirst</span><span class="token punctuation">(</span><span class="token class-name">E</span> e<span class="token punctuation">)</span><span class="token punctuation">{</span>
    <span class="token class-name">Node</span> node <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token punctuation">(</span>e<span class="token punctuation">)</span><span class="token punctuation">;</span>
    node<span class="token punctuation">.</span>next <span class="token operator">=</span> head<span class="token punctuation">;</span>
    head <span class="token operator">=</span> node<span class="token punctuation">;</span>
    size <span class="token operator">++</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre></div><p>上面的代码可以优化如下：</p> <div class="language-java extra-class"><pre class="language-java"><code><span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">addFirst</span><span class="token punctuation">(</span><span class="token class-name">E</span> e<span class="token punctuation">)</span><span class="token punctuation">{</span>
  head <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token punctuation">(</span>e<span class="token punctuation">,</span> head<span class="token punctuation">)</span><span class="token punctuation">;</span>
  size <span class="token operator">++</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre></div><p>当我们执行<code>new Node(e, head)</code>时，会执行Node类的构造函数，将head传给构造函数的next并创建一个node节点，此时新创建节点的next就指向了head，<code>head = new Node(e, head)</code>将head指向了这个新节点。</p> <p><img src="/assets/img/5.9a661a50.png" alt=""></p> <h3 id="在链表中间插入元素"><a href="#在链表中间插入元素" class="header-anchor">#</a> 在链表中间插入元素</h3> <p>如图，我们想将node节点插入到索引为2的地方，需要先找到要添加节点位置的前的一个节点也就是prev节点，然后将node节点的next指向prev指向的下一个节点，再将prev节点的next指向node节点即可。</p> <p><img src="" alt=""></p> <p>注意在链表的操作过程中顺序是很重要的，这个例子中节点指向不能写成这样：</p> <div class="language- extra-class"><pre class="language-text"><code>prev.next = node
node = prev.next
</code></pre></div><p>上面这样写，prev.next已经指向了node节点，再将node节点指向node节点本身。</p> <p>下面我们来实现下向链表中特定位置插入节点的方法：</p> <div class="language-java extra-class"><pre class="language-java"><code><span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">add</span><span class="token punctuation">(</span><span class="token keyword">int</span> index<span class="token punctuation">,</span> <span class="token class-name">E</span> e<span class="token punctuation">)</span><span class="token punctuation">{</span>
    <span class="token comment">// index &gt; size 表示index是可以取到size的也就是向链表的末尾添加节点</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>index <span class="token operator">&lt;</span> <span class="token number">0</span> <span class="token operator">||</span> index <span class="token operator">&gt;</span> size<span class="token punctuation">)</span>
        <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">IllegalArgumentException</span><span class="token punctuation">(</span><span class="token string">&quot;Add failed. Illegal index.&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment">// 向链表头添加一个节点</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>index <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span>
        <span class="token function">addFirst</span><span class="token punctuation">(</span>e<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">else</span><span class="token punctuation">{</span>

        <span class="token class-name">Node</span> prev <span class="token operator">=</span> head<span class="token punctuation">;</span>
        <span class="token comment">// index - 1 表示找index位置的前一个位置的节点</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> i <span class="token operator">&lt;</span> index <span class="token operator">-</span> <span class="token number">1</span> <span class="token punctuation">;</span> i <span class="token operator">++</span><span class="token punctuation">)</span>
            <span class="token comment">// prev一直向前移动，一直移动到index-1这个位置，也就是要插入位置的前一个节点</span>
            prev <span class="token operator">=</span> prev<span class="token punctuation">.</span>next<span class="token punctuation">;</span>

        <span class="token comment">// 插入节点</span>
        <span class="token comment">// Node node = new Node(e);</span>
        <span class="token comment">// node.next = prev.next;</span>
        <span class="token comment">// prev.next = node;</span>

        <span class="token comment">// 上面三行插入相关的代码可以简写如下，表示先新建一个节点然后将这个新节点的next指向prev.next，再将prev.next指向这个新节点：</span>
        prev<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token punctuation">(</span>e<span class="token punctuation">,</span> prev<span class="token punctuation">.</span>next<span class="token punctuation">)</span><span class="token punctuation">;</span>

        size <span class="token operator">++</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><h3 id="向链表末尾插入节点"><a href="#向链表末尾插入节点" class="header-anchor">#</a> 向链表末尾插入节点</h3> <p>由于上面我们已将实现了向链表中插入节点的add方法，向链表末尾插入节点可以直接调用add方法完成添加。</p> <div class="language-java extra-class"><pre class="language-java"><code><span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">addLast</span><span class="token punctuation">(</span><span class="token class-name">E</span> e<span class="token punctuation">)</span><span class="token punctuation">{</span>
    <span class="token function">add</span><span class="token punctuation">(</span>size<span class="token punctuation">,</span> e<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre></div><p>上述所实现方法的完整代码如下：</p> <div class="language-java extra-class"><pre class="language-java"><code><span class="token keyword">public</span> <span class="token keyword">class</span> <span class="token class-name">LinkedList</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">E</span><span class="token punctuation">&gt;</span></span> <span class="token punctuation">{</span>

    <span class="token keyword">private</span> <span class="token keyword">class</span> <span class="token class-name">Node</span><span class="token punctuation">{</span>
        <span class="token keyword">public</span> <span class="token class-name">E</span> e<span class="token punctuation">;</span>
        <span class="token keyword">public</span> <span class="token class-name">Node</span> next<span class="token punctuation">;</span>

        <span class="token keyword">public</span> <span class="token class-name">Node</span><span class="token punctuation">(</span><span class="token class-name">E</span> e<span class="token punctuation">,</span> <span class="token class-name">Node</span> next<span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">this</span><span class="token punctuation">.</span>e <span class="token operator">=</span> e<span class="token punctuation">;</span>
            <span class="token keyword">this</span><span class="token punctuation">.</span>next <span class="token operator">=</span> next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">public</span> <span class="token class-name">Node</span><span class="token punctuation">(</span><span class="token class-name">E</span> e<span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">this</span><span class="token punctuation">(</span>e<span class="token punctuation">,</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">public</span> <span class="token class-name">Node</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">this</span><span class="token punctuation">(</span><span class="token keyword">null</span><span class="token punctuation">,</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token annotation punctuation">@Override</span>
        <span class="token keyword">public</span> <span class="token class-name">String</span> <span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">return</span> e<span class="token punctuation">.</span><span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 存储链表头</span>
    <span class="token keyword">private</span> <span class="token class-name">Node</span> head<span class="token punctuation">;</span>
    <span class="token comment">// 记录链表中一共存储了多少元素</span>
    <span class="token keyword">private</span> <span class="token keyword">int</span> size<span class="token punctuation">;</span>

    <span class="token keyword">public</span> <span class="token class-name">LinkedList</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        head <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        size <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 获取链表中的元素个数</span>
    <span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">getSize</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">return</span> size<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 返回链表是否为空</span>
    <span class="token keyword">public</span> <span class="token keyword">boolean</span> <span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">return</span> size <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 在链表头添加新的元素e</span>
    <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">addFirst</span><span class="token punctuation">(</span><span class="token class-name">E</span> e<span class="token punctuation">)</span><span class="token punctuation">{</span>
<span class="token comment">//        Node node = new Node(e);</span>
<span class="token comment">//        node.next = head;</span>
<span class="token comment">//        head = node;</span>

        head <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token punctuation">(</span>e<span class="token punctuation">,</span> head<span class="token punctuation">)</span><span class="token punctuation">;</span>
        size <span class="token operator">++</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 在链表的index(0-based)位置添加新的元素e</span>
    <span class="token comment">// 在链表中不是一个常用的操作，练习用：）</span>
    <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">add</span><span class="token punctuation">(</span><span class="token keyword">int</span> index<span class="token punctuation">,</span> <span class="token class-name">E</span> e<span class="token punctuation">)</span><span class="token punctuation">{</span>

        <span class="token keyword">if</span><span class="token punctuation">(</span>index <span class="token operator">&lt;</span> <span class="token number">0</span> <span class="token operator">||</span> index <span class="token operator">&gt;</span> size<span class="token punctuation">)</span>
            <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">IllegalArgumentException</span><span class="token punctuation">(</span><span class="token string">&quot;Add failed. Illegal index.&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">if</span><span class="token punctuation">(</span>index <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span>
            <span class="token function">addFirst</span><span class="token punctuation">(</span>e<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">else</span><span class="token punctuation">{</span>
            <span class="token class-name">Node</span> prev <span class="token operator">=</span> head<span class="token punctuation">;</span>
            <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> i <span class="token operator">&lt;</span> index <span class="token operator">-</span> <span class="token number">1</span> <span class="token punctuation">;</span> i <span class="token operator">++</span><span class="token punctuation">)</span>
                prev <span class="token operator">=</span> prev<span class="token punctuation">.</span>next<span class="token punctuation">;</span>

<span class="token comment">//            Node node = new Node(e);</span>
<span class="token comment">//            node.next = prev.next;</span>
<span class="token comment">//            prev.next = node;</span>

            prev<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token punctuation">(</span>e<span class="token punctuation">,</span> prev<span class="token punctuation">.</span>next<span class="token punctuation">)</span><span class="token punctuation">;</span>
            size <span class="token operator">++</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 在链表末尾添加新的元素e</span>
    <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">addLast</span><span class="token punctuation">(</span><span class="token class-name">E</span> e<span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token function">add</span><span class="token punctuation">(</span>size<span class="token punctuation">,</span> e<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><h2 id="链表虚拟头节点"><a href="#链表虚拟头节点" class="header-anchor">#</a> 链表虚拟头节点</h2> <p>前面我们实现了向链表中添加节点的add方法，其中对向链表头添加元素做了特殊处理</p> <div class="language-java extra-class"><pre class="language-java"><code><span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">add</span><span class="token punctuation">(</span><span class="token keyword">int</span> index<span class="token punctuation">,</span> <span class="token class-name">E</span> e<span class="token punctuation">)</span><span class="token punctuation">{</span>
    <span class="token comment">// ...</span>

    <span class="token comment">// 向链表头添加元素</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>index <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span>
        <span class="token function">addFirst</span><span class="token punctuation">(</span>e<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">else</span><span class="token punctuation">{</span>
      <span class="token comment">// ...</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><p>为什么向链表头添加元素要做特殊处理呢？是因为我们向链表中添加节点时需要找到待添加位置之前的那个节点，但是对于链表头来说它没有前面的那个节点，所以逻辑上会特殊处理。</p> <p>在链表的具体实现中有一个非常常用的技巧，可以将链表头的操作和其他操作统一起来。链表头之所以要链表头不是没有前置节点吗，我们就造一个前置节点，它不存储任意元素，将这个空节点当做链表的头也就是虚拟头节点。这样对于链表来说第一个元素就是这个空节点next所指向的节点，这个空节点只是为了便于编写代码。
<img src="" alt=""></p> <p>代码实现：</p> <div class="language-java extra-class"><pre class="language-java"><code><span class="token keyword">public</span> <span class="token keyword">class</span> <span class="token class-name">LinkedList</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">E</span><span class="token punctuation">&gt;</span></span> <span class="token punctuation">{</span>

    <span class="token keyword">private</span> <span class="token keyword">class</span> <span class="token class-name">Node</span><span class="token punctuation">{</span>
        <span class="token keyword">public</span> <span class="token class-name">E</span> e<span class="token punctuation">;</span>
        <span class="token keyword">public</span> <span class="token class-name">Node</span> next<span class="token punctuation">;</span>

        <span class="token keyword">public</span> <span class="token class-name">Node</span><span class="token punctuation">(</span><span class="token class-name">E</span> e<span class="token punctuation">,</span> <span class="token class-name">Node</span> next<span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">this</span><span class="token punctuation">.</span>e <span class="token operator">=</span> e<span class="token punctuation">;</span>
            <span class="token keyword">this</span><span class="token punctuation">.</span>next <span class="token operator">=</span> next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">public</span> <span class="token class-name">Node</span><span class="token punctuation">(</span><span class="token class-name">E</span> e<span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">this</span><span class="token punctuation">(</span>e<span class="token punctuation">,</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">public</span> <span class="token class-name">Node</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">this</span><span class="token punctuation">(</span><span class="token keyword">null</span><span class="token punctuation">,</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token annotation punctuation">@Override</span>
        <span class="token keyword">public</span> <span class="token class-name">String</span> <span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">return</span> e<span class="token punctuation">.</span><span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token comment">// 虚拟头节点</span>
    <span class="token keyword">private</span> <span class="token class-name">Node</span> dummyHead<span class="token punctuation">;</span>
    <span class="token keyword">private</span> <span class="token keyword">int</span> size<span class="token punctuation">;</span>

    <span class="token keyword">public</span> <span class="token class-name">LinkedList</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token comment">// 此时对于一个空的链表来说它是存在一个节点的</span>
        dummyHead <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        size <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 获取链表中的元素个数</span>
    <span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">getSize</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">return</span> size<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 返回链表是否为空</span>
    <span class="token keyword">public</span> <span class="token keyword">boolean</span> <span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">return</span> size <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 在链表的index(0-based)位置添加新的元素e</span>
    <span class="token comment">// 在链表中不是一个常用的操作，练习用：）</span>
    <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">add</span><span class="token punctuation">(</span><span class="token keyword">int</span> index<span class="token punctuation">,</span> <span class="token class-name">E</span> e<span class="token punctuation">)</span><span class="token punctuation">{</span>

        <span class="token keyword">if</span><span class="token punctuation">(</span>index <span class="token operator">&lt;</span> <span class="token number">0</span> <span class="token operator">||</span> index <span class="token operator">&gt;</span> size<span class="token punctuation">)</span>
            <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">IllegalArgumentException</span><span class="token punctuation">(</span><span class="token string">&quot;Add failed. Illegal index.&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token comment">// 初始是从dummyHead开始的，指向的是0这个节点之前的节点</span>
        <span class="token class-name">Node</span> prev <span class="token operator">=</span> dummyHead<span class="token punctuation">;</span>

        <span class="token comment">// 因为是从dummyHead开始的所以需要遍历index次</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> i <span class="token operator">&lt;</span> index <span class="token punctuation">;</span> i <span class="token operator">++</span><span class="token punctuation">)</span>
            prev <span class="token operator">=</span> prev<span class="token punctuation">.</span>next<span class="token punctuation">;</span>

        prev<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token punctuation">(</span>e<span class="token punctuation">,</span> prev<span class="token punctuation">.</span>next<span class="token punctuation">)</span><span class="token punctuation">;</span>
        size <span class="token operator">++</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 在链表头添加新的元素e</span>
    <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">addFirst</span><span class="token punctuation">(</span><span class="token class-name">E</span> e<span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token function">add</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span> e<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 在链表末尾添加新的元素e</span>
    <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">addLast</span><span class="token punctuation">(</span><span class="token class-name">E</span> e<span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token function">add</span><span class="token punctuation">(</span>size<span class="token punctuation">,</span> e<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><h2 id="链表的遍历、查询和修改"><a href="#链表的遍历、查询和修改" class="header-anchor">#</a> 链表的遍历、查询和修改</h2> <p>下面来实现获取链表中第index位置的元素，由于在链表中不常使用索引，所以这个方法只是个练习，为了更好的熟悉操作链表。</p> <p>前面我们已经实现了给链表指定位置添加元素的add方法，现在我们要实现的是获取指定元素的方法，添加元素是遍历的链表中index位置的前一个元素，获取元素是获取index位置的元素，操作方法类似，只需要将add方法稍作修改即可。</p> <div class="language-java extra-class"><pre class="language-java"><code><span class="token comment">// 获得链表的第index(0-based)个位置的元素</span>
<span class="token comment">// 在链表中不是一个常用的操作，练习用：）</span>
<span class="token keyword">public</span> <span class="token class-name">E</span> <span class="token function">get</span><span class="token punctuation">(</span><span class="token keyword">int</span> index<span class="token punctuation">)</span><span class="token punctuation">{</span>
    <span class="token comment">// 判断index的合法性</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>index <span class="token operator">&lt;</span> <span class="token number">0</span> <span class="token operator">||</span> index <span class="token operator">&gt;=</span> size<span class="token punctuation">)</span>
        <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">IllegalArgumentException</span><span class="token punctuation">(</span><span class="token string">&quot;Get failed. Illegal index.&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token comment">// 从索引为零的位置开始</span>
    <span class="token class-name">Node</span> cur <span class="token operator">=</span> dummyHead<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
    <span class="token comment">// 遍历index次</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> i <span class="token operator">&lt;</span> index <span class="token punctuation">;</span> i <span class="token operator">++</span><span class="token punctuation">)</span>
        cur <span class="token operator">=</span> cur<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
    <span class="token keyword">return</span> cur<span class="token punctuation">.</span>e<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre></div><p>下面实现获取链表中第一个元素及最后一个元素的方法，可以直接调用上面的get方法，这里直接列出</p> <div class="language-java extra-class"><pre class="language-java"><code><span class="token comment">// 获得链表的第一个元素</span>
<span class="token keyword">public</span> <span class="token class-name">E</span> <span class="token function">getFirst</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
    <span class="token keyword">return</span> <span class="token function">get</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token comment">// 获得链表的最后一个元素</span>
<span class="token keyword">public</span> <span class="token class-name">E</span> <span class="token function">getLast</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
    <span class="token keyword">return</span> <span class="token function">get</span><span class="token punctuation">(</span>size <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre></div><p>修改指定位置的元素和获取的逻辑基本类似，只不过一个找节点后返回，一个是给这个节点重新赋值</p> <div class="language-java extra-class"><pre class="language-java"><code><span class="token comment">// 修改链表的第index(0-based)个位置的元素为e</span>
<span class="token comment">// 在链表中不是一个常用的操作，练习用：）</span>
<span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">set</span><span class="token punctuation">(</span><span class="token keyword">int</span> index<span class="token punctuation">,</span> <span class="token class-name">E</span> e<span class="token punctuation">)</span><span class="token punctuation">{</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>index <span class="token operator">&lt;</span> <span class="token number">0</span> <span class="token operator">||</span> index <span class="token operator">&gt;=</span> size<span class="token punctuation">)</span>
        <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">IllegalArgumentException</span><span class="token punctuation">(</span><span class="token string">&quot;Set failed. Illegal index.&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token class-name">Node</span> cur <span class="token operator">=</span> dummyHead<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> i <span class="token operator">&lt;</span> index <span class="token punctuation">;</span> i <span class="token operator">++</span><span class="token punctuation">)</span>
        cur <span class="token operator">=</span> cur<span class="token punctuation">.</span>next<span class="token punctuation">;</span>

    cur<span class="token punctuation">.</span>e <span class="token operator">=</span> e<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre></div><p>查找链表中是否包含指定节点，思路：从链表开头依次遍历到链表末尾，看看其中是否有节点和这个节点相等，如果相等返回true，如果没有就返回false。</p> <div class="language-java extra-class"><pre class="language-java"><code><span class="token comment">// 查找链表中是否有元素e</span>
<span class="token keyword">public</span> <span class="token keyword">boolean</span> <span class="token function">contains</span><span class="token punctuation">(</span><span class="token class-name">E</span> e<span class="token punctuation">)</span><span class="token punctuation">{</span>
    <span class="token class-name">Node</span> cur <span class="token operator">=</span> dummyHead<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>cur <span class="token operator">!=</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>cur<span class="token punctuation">.</span>e<span class="token punctuation">.</span><span class="token function">equals</span><span class="token punctuation">(</span>e<span class="token punctuation">)</span><span class="token punctuation">)</span>
            <span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span>

        cur <span class="token operator">=</span> cur<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre></div><h2 id="从链表中删除元素"><a href="#从链表中删除元素" class="header-anchor">#</a> 从链表中删除元素</h2> <p>查找到待删除节点的前一个节点prev，然后将pre.next指向待删除节点的next，也就是跳过这个待删除的节点，这样操作后，因为遍历不到这个待删除的节点了，也就等同于将这个节点删除了。为了方便计算机回收这个待删除的节点的空间需要将delNode.next指向null，使它和整个链表脱离开。</p> <p><img src="/assets/img/8.7b989781.png" alt=""></p> <p>删除指定位置的节点代码实现：</p> <div class="language-java extra-class"><pre class="language-java"><code><span class="token comment">// 从链表中删除index(0-based)位置的元素, 返回删除的元素</span>
<span class="token comment">// 在链表中不是一个常用的操作，练习用：）</span>
<span class="token keyword">public</span> <span class="token class-name">E</span> <span class="token function">remove</span><span class="token punctuation">(</span><span class="token keyword">int</span> index<span class="token punctuation">)</span><span class="token punctuation">{</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>index <span class="token operator">&lt;</span> <span class="token number">0</span> <span class="token operator">||</span> index <span class="token operator">&gt;=</span> size<span class="token punctuation">)</span>
        <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">IllegalArgumentException</span><span class="token punctuation">(</span><span class="token string">&quot;Remove failed. Index is illegal.&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token comment">// 找到待删除节点之前的节点，所以prev是从dummyHead开始</span>
    <span class="token class-name">Node</span> prev <span class="token operator">=</span> dummyHead<span class="token punctuation">;</span>

    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> i <span class="token operator">&lt;</span> index <span class="token punctuation">;</span> i <span class="token operator">++</span><span class="token punctuation">)</span>
        prev <span class="token operator">=</span> prev<span class="token punctuation">.</span>next<span class="token punctuation">;</span>

    <span class="token comment">// 删除节点</span>
    <span class="token class-name">Node</span> retNode <span class="token operator">=</span> prev<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
    prev<span class="token punctuation">.</span>next <span class="token operator">=</span> retNode<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
    retNode<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>

    size <span class="token operator">--</span><span class="token punctuation">;</span>

    <span class="token keyword">return</span> retNode<span class="token punctuation">.</span>e<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre></div><p>从链表中删除第一个节点、从链表中删除最后一个节点</p> <div class="language-java extra-class"><pre class="language-java"><code><span class="token comment">// 从链表中删除第一个元素, 返回删除的元素</span>
<span class="token keyword">public</span> <span class="token class-name">E</span> <span class="token function">removeFirst</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
    <span class="token keyword">return</span> <span class="token function">remove</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token comment">// 从链表中删除最后一个元素, 返回删除的元素</span>
<span class="token keyword">public</span> <span class="token class-name">E</span> <span class="token function">removeLast</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
    <span class="token keyword">return</span> <span class="token function">remove</span><span class="token punctuation">(</span>size <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre></div><div class="language-java extra-class"><pre class="language-java"><code><span class="token comment">// 从链表中删除元素e</span>
<span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">removeElement</span><span class="token punctuation">(</span><span class="token class-name">E</span> e<span class="token punctuation">)</span><span class="token punctuation">{</span>

    <span class="token class-name">Node</span> prev <span class="token operator">=</span> dummyHead<span class="token punctuation">;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>prev<span class="token punctuation">.</span>next <span class="token operator">!=</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>prev<span class="token punctuation">.</span>next<span class="token punctuation">.</span>e<span class="token punctuation">.</span><span class="token function">equals</span><span class="token punctuation">(</span>e<span class="token punctuation">)</span><span class="token punctuation">)</span>
            <span class="token keyword">break</span><span class="token punctuation">;</span>
        prev <span class="token operator">=</span> prev<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">if</span><span class="token punctuation">(</span>prev<span class="token punctuation">.</span>next <span class="token operator">!=</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token class-name">Node</span> delNode <span class="token operator">=</span> prev<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        prev<span class="token punctuation">.</span>next <span class="token operator">=</span> delNode<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        delNode<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        size <span class="token operator">--</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><p>下面展示一个错误的删除逻辑：</p> <p><img src="/assets/img/9.ef051c75.png" alt=""></p> <p>用cur变量找到要删除的节点，然后将cur指向cur.next这个节点，这样并不能删除待删除的节点，只不过是将变量cur指向了待删除节点的下一个节点而已。如果想让链表发生改变，必须把链表中相应节点的next做变化，而不是让某个一节点变量发生变化。</p> <h3 id="链表的时间复杂度分析"><a href="#链表的时间复杂度分析" class="header-anchor">#</a> 链表的时间复杂度分析</h3> <table><thead><tr><th>方法名</th> <th>时间复杂度</th> <th>备注</th></tr></thead> <tbody><tr><td>addLast(e)</td> <td>O(n)</td> <td></td></tr> <tr><td>addFirst(e)</td> <td>O(1)</td> <td></td></tr> <tr><td>add(index, e)</td> <td>O(n)</td> <td></td></tr> <tr><td>removeLast(e)</td> <td>O(n)</td> <td></td></tr> <tr><td>removeFirst(e)</td> <td>O(1)</td> <td></td></tr> <tr><td>remove(index, e)</td> <td>O(n)</td> <td></td></tr> <tr><td>set(index, e)</td> <td>O(n)</td> <td></td></tr> <tr><td>get(index)</td> <td>O(n)</td> <td></td></tr> <tr><td>contains(e)</td> <td>O(n)</td> <td></td></tr></tbody></table> <p>对于链表来说，增、删、改、查这四个操作它的时间复杂度都是O(n)的，但是如果我们只对链表头进行操作它的时间复杂度是O(1)级别的。由于链表整体是动态的，所以不会大量的浪费内存空间，链表是一种最基础的动态数据结构，熟练掌握链表，对于学习其他动态的数据结构有很大帮助。</p> <h2 id="使用链表实现栈"><a href="#使用链表实现栈" class="header-anchor">#</a> 使用链表实现栈</h2> <p>如果我们只对链表的头进行增、删的话时间复杂度是O(1)的，如果我们只查链表头的元素，时间复杂度也是O(1)的。是不是和之前介绍栈这种数据结构类似呢。所以对应链表，我们可以将链表头当做栈顶，用链表作为栈的底层实现，来实现栈这种的数据结构。</p> <p>由于用链表实现栈这种数据结构都是调用的上面我们提到的链表操作方法，这里直接给出具体实现代码：</p> <div class="language-java extra-class"><pre class="language-java"><code><span class="token keyword">public</span> <span class="token keyword">class</span> <span class="token class-name">LinkedListStack</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">E</span><span class="token punctuation">&gt;</span></span> <span class="token keyword">implements</span> <span class="token class-name">Stack</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">E</span><span class="token punctuation">&gt;</span></span> <span class="token punctuation">{</span>

    <span class="token keyword">private</span> <span class="token class-name">LinkedList</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">E</span><span class="token punctuation">&gt;</span></span> list<span class="token punctuation">;</span>

    <span class="token comment">// 因为链表没有容积这个概念，所以构造函数只有这一个就够了</span>
    <span class="token keyword">public</span> <span class="token class-name">LinkedListStack</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        list <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">LinkedList</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token punctuation">&gt;</span></span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token annotation punctuation">@Override</span>
    <span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">getSize</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">return</span> list<span class="token punctuation">.</span><span class="token function">getSize</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token annotation punctuation">@Override</span>
    <span class="token keyword">public</span> <span class="token keyword">boolean</span> <span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">return</span> list<span class="token punctuation">.</span><span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token annotation punctuation">@Override</span>
    <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">push</span><span class="token punctuation">(</span><span class="token class-name">E</span> e<span class="token punctuation">)</span><span class="token punctuation">{</span>
        list<span class="token punctuation">.</span><span class="token function">addFirst</span><span class="token punctuation">(</span>e<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token annotation punctuation">@Override</span>
    <span class="token keyword">public</span> <span class="token class-name">E</span> <span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">return</span> list<span class="token punctuation">.</span><span class="token function">removeFirst</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token annotation punctuation">@Override</span>
    <span class="token keyword">public</span> <span class="token class-name">E</span> <span class="token function">peek</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">return</span> list<span class="token punctuation">.</span><span class="token function">getFirst</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token annotation punctuation">@Override</span>
    <span class="token keyword">public</span> <span class="token class-name">String</span> <span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token class-name">StringBuilder</span> res <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">StringBuilder</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        res<span class="token punctuation">.</span><span class="token function">append</span><span class="token punctuation">(</span><span class="token string">&quot;Stack: top &quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        res<span class="token punctuation">.</span><span class="token function">append</span><span class="token punctuation">(</span>list<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> res<span class="token punctuation">.</span><span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token class-name">String</span><span class="token punctuation">[</span><span class="token punctuation">]</span> args<span class="token punctuation">)</span> <span class="token punctuation">{</span>

        <span class="token class-name">LinkedListStack</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">Integer</span><span class="token punctuation">&gt;</span></span> stack <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">LinkedListStack</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token punctuation">&gt;</span></span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> i <span class="token operator">&lt;</span> <span class="token number">5</span> <span class="token punctuation">;</span> i <span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            stack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>stack<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        stack<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>stack<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><p>上面我们用链表实现了栈这种数据结构，之前我们用数组也实现了栈这种数据结构，那么这两种实现方式哪种更好呢？</p> <p>测试两种实现栈方法的性能：</p> <div class="language-java extra-class"><pre class="language-java"><code><span class="token keyword">import</span> <span class="token namespace">java<span class="token punctuation">.</span>util<span class="token punctuation">.</span></span><span class="token class-name">Random</span><span class="token punctuation">;</span>

<span class="token keyword">public</span> <span class="token keyword">class</span> <span class="token class-name">Main</span> <span class="token punctuation">{</span>

    <span class="token comment">// 测试使用stack运行opCount个push和pop操作所需要的时间，单位：秒</span>
    <span class="token keyword">private</span> <span class="token keyword">static</span> <span class="token keyword">double</span> <span class="token function">testStack</span><span class="token punctuation">(</span><span class="token class-name">Stack</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">Integer</span><span class="token punctuation">&gt;</span></span> stack<span class="token punctuation">,</span> <span class="token keyword">int</span> opCount<span class="token punctuation">)</span><span class="token punctuation">{</span>

        <span class="token keyword">long</span> startTime <span class="token operator">=</span> <span class="token class-name">System</span><span class="token punctuation">.</span><span class="token function">nanoTime</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token class-name">Random</span> random <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Random</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> i <span class="token operator">&lt;</span> opCount <span class="token punctuation">;</span> i <span class="token operator">++</span><span class="token punctuation">)</span>
            stack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>random<span class="token punctuation">.</span><span class="token function">nextInt</span><span class="token punctuation">(</span><span class="token class-name">Integer</span><span class="token punctuation">.</span>MAX_VALUE<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> i <span class="token operator">&lt;</span> opCount <span class="token punctuation">;</span> i <span class="token operator">++</span><span class="token punctuation">)</span>
            stack<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">long</span> endTime <span class="token operator">=</span> <span class="token class-name">System</span><span class="token punctuation">.</span><span class="token function">nanoTime</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">return</span> <span class="token punctuation">(</span>endTime <span class="token operator">-</span> startTime<span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token number">1000000000.0</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token class-name">String</span><span class="token punctuation">[</span><span class="token punctuation">]</span> args<span class="token punctuation">)</span> <span class="token punctuation">{</span>

        <span class="token keyword">int</span> opCount <span class="token operator">=</span> <span class="token number">100000</span><span class="token punctuation">;</span>

        <span class="token class-name">ArrayStack</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">Integer</span><span class="token punctuation">&gt;</span></span> arrayStack <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">ArrayStack</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token punctuation">&gt;</span></span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">double</span> time1 <span class="token operator">=</span> <span class="token function">testStack</span><span class="token punctuation">(</span>arrayStack<span class="token punctuation">,</span> opCount<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">&quot;ArrayStack, time: &quot;</span> <span class="token operator">+</span> time1 <span class="token operator">+</span> <span class="token string">&quot; s&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token class-name">LinkedListStack</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">Integer</span><span class="token punctuation">&gt;</span></span> linkedListStack <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">LinkedListStack</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token punctuation">&gt;</span></span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">double</span> time2 <span class="token operator">=</span> <span class="token function">testStack</span><span class="token punctuation">(</span>linkedListStack<span class="token punctuation">,</span> opCount<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">&quot;LinkedListStack, time: &quot;</span> <span class="token operator">+</span> time2 <span class="token operator">+</span> <span class="token string">&quot; s&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token comment">// 其实这个时间比较很复杂，因为LinkedListStack中包含更多的new操作</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><p>链表实现的栈要比数组实现栈速度更快些。因为对于数组栈来说需要resize，这个过程是比较耗时的，而链表栈并不存在这种情况。但这个结果不是一定的，因为对于链表栈来说要不停的new Node，包含更多的new操作，new操作在不同的系统上可能比较耗时，因为在不停的在寻找开辟空间的地方，通常操作越多，new操作耗时越明显。实际上不管是Array stack还是链表栈它们的各项操作在实现中都是同一复杂度的，它们之间没有复杂度上的巨大差异。</p> <h2 id="使用链表实现队列"><a href="#使用链表实现队列" class="header-anchor">#</a> 使用链表实现队列</h2> <p>前面我们使用链表实现了栈这种数据结构，那么能不能使用链表实现队列这种数据结构呢？</p> <p>前面我们知道对于链表头的增删时间复杂度是O(1)级别的，对于链表尾部的操作时间复杂度是O(n)级别的。可见用链表实现队列，队列的一端时间复杂度会是O(n)级别的。</p> <p>有没有什么方法可以优化下呢？</p> <p>这里我们思考下为什么说在链表头部增删元素比较简单呢？这是因为我们有head这样一个变量帮我们标记链表的头在哪，这样的话是否可以有个变量来记录链表尾部的位置呢？如果有了这个标记尾部的变量那在链表尾部添加节点就会变的很容易，但是对于从链表尾部删除一个节点还是比较复杂的，因为需要找到待删除节点的前一个节点。</p> <p>综上，当我们分别有一个变量标记链表的头部，一个变量标记链表的尾部时，对于链表头部的操作时间复杂度都是O(1)级别的，对于链表尾部只有增加节点的时间复杂度是O(1)级别的。这样看来我们可以用链表的头部当做队首负责出队，用链表的尾部当做队尾负责入队。</p> <p><img src="" alt=""></p> <p>由于我们只对队尾和队首进行操作，不涉及对中间元素进行操作，所以链表不必包含虚拟头节点，但是这样要注意链表为空的情况，也就是链表头部和尾部都指向空。</p> <p><img src="/assets/img/11.ae4fa04b.png" alt=""></p> <p>实现入队操作：</p> <div class="language-java extra-class"><pre class="language-java"><code><span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">enqueue</span><span class="token punctuation">(</span><span class="token class-name">E</span> e<span class="token punctuation">)</span><span class="token punctuation">{</span>
    <span class="token comment">// tail为空，说明链表为空</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>tail <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        tail <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token punctuation">(</span>e<span class="token punctuation">)</span><span class="token punctuation">;</span>
        head <span class="token operator">=</span> tail<span class="token punctuation">;</span>
    <span class="token punctuation">}</span><span class="token keyword">else</span> <span class="token punctuation">{</span> <span class="token comment">// 链表不为空</span>
        <span class="token comment">// tail的next指向新节点</span>
        tail<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token punctuation">(</span>e<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token comment">// 将tail移动到新节点位置</span>
        tail <span class="token operator">=</span> tail<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    size <span class="token operator">++</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre></div><p>对于出队操作我们需要考虑三种情况：</p> <ol><li>链表为空，这种情况直接返回即可，不需要执行出队操作</li> <li>链表中只有一个元素</li> <li>链表中有多个元素</li></ol> <p>针对情况2、3我们需要先创建一个新的节点，指向head节点，然后将head节点指向它的下一个节点，再然后将新建的这个节点的next置为空使它脱离链表。对于链表中只有一个元素的情况，执行完上述操作后，还要将tail置为空，要不tail还会指向出队的节点。</p> <p><img src="/assets/img/12.643f704b.png" alt="">
出队：</p> <div class="language-java extra-class"><pre class="language-java"><code><span class="token keyword">public</span> <span class="token class-name">E</span> <span class="token function">dequeue</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
    <span class="token comment">// 处理链表为空的情况</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
        <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">IllegalArgumentException</span><span class="token punctuation">(</span><span class="token string">&quot;Cannot dequeue from an empty queue.&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

    <span class="token class-name">Node</span> retNode <span class="token operator">=</span> head<span class="token punctuation">;</span>
    head <span class="token operator">=</span> head<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
    retNode<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
    
    <span class="token comment">// 处理链表中只有一个节点的情况</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>head <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span>
        tail <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>

    size <span class="token operator">--</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> retNode<span class="token punctuation">.</span>e<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre></div><p>使用链表实现队列的完整代码如下：</p> <div class="language-java extra-class"><pre class="language-java"><code><span class="token keyword">public</span> <span class="token keyword">class</span> <span class="token class-name">LinkedListQueue</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">E</span><span class="token punctuation">&gt;</span></span> <span class="token keyword">implements</span> <span class="token class-name">Queue</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">E</span><span class="token punctuation">&gt;</span></span> <span class="token punctuation">{</span>

    <span class="token keyword">private</span> <span class="token keyword">class</span> <span class="token class-name">Node</span><span class="token punctuation">{</span>
        <span class="token keyword">public</span> <span class="token class-name">E</span> e<span class="token punctuation">;</span>
        <span class="token keyword">public</span> <span class="token class-name">Node</span> next<span class="token punctuation">;</span>

        <span class="token keyword">public</span> <span class="token class-name">Node</span><span class="token punctuation">(</span><span class="token class-name">E</span> e<span class="token punctuation">,</span> <span class="token class-name">Node</span> next<span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">this</span><span class="token punctuation">.</span>e <span class="token operator">=</span> e<span class="token punctuation">;</span>
            <span class="token keyword">this</span><span class="token punctuation">.</span>next <span class="token operator">=</span> next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">public</span> <span class="token class-name">Node</span><span class="token punctuation">(</span><span class="token class-name">E</span> e<span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">this</span><span class="token punctuation">(</span>e<span class="token punctuation">,</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">public</span> <span class="token class-name">Node</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">this</span><span class="token punctuation">(</span><span class="token keyword">null</span><span class="token punctuation">,</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token annotation punctuation">@Override</span>
        <span class="token keyword">public</span> <span class="token class-name">String</span> <span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">return</span> e<span class="token punctuation">.</span><span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// head记录头节点 tail记录尾节点</span>
    <span class="token keyword">private</span> <span class="token class-name">Node</span> head<span class="token punctuation">,</span> tail<span class="token punctuation">;</span>
    <span class="token comment">// 记录链表中存储了多少元素</span>
    <span class="token keyword">private</span> <span class="token keyword">int</span> size<span class="token punctuation">;</span>

    <span class="token keyword">public</span> <span class="token class-name">LinkedListQueue</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        head <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        tail <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        size <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token annotation punctuation">@Override</span>
    <span class="token keyword">public</span> <span class="token keyword">int</span> <span class="token function">getSize</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">return</span> size<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token annotation punctuation">@Override</span>
    <span class="token keyword">public</span> <span class="token keyword">boolean</span> <span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">return</span> size <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token annotation punctuation">@Override</span>
    <span class="token keyword">public</span> <span class="token keyword">void</span> <span class="token function">enqueue</span><span class="token punctuation">(</span><span class="token class-name">E</span> e<span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token comment">// tail为空，说明链表为空</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>tail <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            tail <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token punctuation">(</span>e<span class="token punctuation">)</span><span class="token punctuation">;</span>
            head <span class="token operator">=</span> tail<span class="token punctuation">;</span>
        <span class="token punctuation">}</span><span class="token keyword">else</span> <span class="token punctuation">{</span> <span class="token comment">// 链表不为空</span>
            <span class="token comment">// tail的next指向新节点</span>
            tail<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token punctuation">(</span>e<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token comment">// 将tail移动到新节点位置</span>
            tail <span class="token operator">=</span> tail<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        size <span class="token operator">++</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token annotation punctuation">@Override</span>
    <span class="token keyword">public</span> <span class="token class-name">E</span> <span class="token function">dequeue</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token comment">// 处理链表为空的情况</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
            <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">IllegalArgumentException</span><span class="token punctuation">(</span><span class="token string">&quot;Cannot dequeue from an empty queue.&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token class-name">Node</span> retNode <span class="token operator">=</span> head<span class="token punctuation">;</span>
        head <span class="token operator">=</span> head<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        retNode<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        
        <span class="token comment">// 处理链表中只有一个节点的情况</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>head <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span>
            tail <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>

        size <span class="token operator">--</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> retNode<span class="token punctuation">.</span>e<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 查看队首元素</span>
    <span class="token annotation punctuation">@Override</span>
    <span class="token keyword">public</span> <span class="token class-name">E</span> <span class="token function">getFront</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
            <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">IllegalArgumentException</span><span class="token punctuation">(</span><span class="token string">&quot;Queue is empty.&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> head<span class="token punctuation">.</span>e<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token annotation punctuation">@Override</span>
    <span class="token keyword">public</span> <span class="token class-name">String</span> <span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        <span class="token class-name">StringBuilder</span> res <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">StringBuilder</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        res<span class="token punctuation">.</span><span class="token function">append</span><span class="token punctuation">(</span><span class="token string">&quot;Queue: front &quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token class-name">Node</span> cur <span class="token operator">=</span> head<span class="token punctuation">;</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span>cur <span class="token operator">!=</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            res<span class="token punctuation">.</span><span class="token function">append</span><span class="token punctuation">(</span>cur <span class="token operator">+</span> <span class="token string">&quot;-&gt;&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            cur <span class="token operator">=</span> cur<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        res<span class="token punctuation">.</span><span class="token function">append</span><span class="token punctuation">(</span><span class="token string">&quot;NULL tail&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> res<span class="token punctuation">.</span><span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token class-name">String</span><span class="token punctuation">[</span><span class="token punctuation">]</span> args<span class="token punctuation">)</span><span class="token punctuation">{</span>

        <span class="token class-name">LinkedListQueue</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token class-name">Integer</span><span class="token punctuation">&gt;</span></span> queue <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">LinkedListQueue</span><span class="token generics"><span class="token punctuation">&lt;</span><span class="token punctuation">&gt;</span></span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> i <span class="token operator">&lt;</span> <span class="token number">10</span> <span class="token punctuation">;</span> i <span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            queue<span class="token punctuation">.</span><span class="token function">enqueue</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>queue<span class="token punctuation">)</span><span class="token punctuation">;</span>

            <span class="token keyword">if</span><span class="token punctuation">(</span>i <span class="token operator">%</span> <span class="token number">3</span> <span class="token operator">==</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                queue<span class="token punctuation">.</span><span class="token function">dequeue</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>queue<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><h2 id="链表真题练习"><a href="#链表真题练习" class="header-anchor">#</a> 链表真题练习</h2> <div class="language- extra-class"><pre class="language-text"><code>删除链表中等于给定值 val 的所有节点。

示例:

输入: 1-&gt;2-&gt;6-&gt;3-&gt;4-&gt;5-&gt;6, val = 6
输出: 1-&gt;2-&gt;3-&gt;4-&gt;5
</code></pre></div><p>方法1：不使用虚拟头节点</p> <div class="language-java extra-class"><pre class="language-java"><code><span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
    <span class="token keyword">public</span> <span class="token class-name">ListNode</span> <span class="token function">removeElements</span><span class="token punctuation">(</span><span class="token class-name">ListNode</span> head<span class="token punctuation">,</span> <span class="token keyword">int</span> val<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">while</span> <span class="token punctuation">(</span>head <span class="token operator">!=</span> <span class="token keyword">null</span> <span class="token operator">&amp;&amp;</span> head<span class="token punctuation">.</span>val <span class="token operator">==</span> val<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token class-name">ListNode</span> delNode <span class="token operator">=</span> head<span class="token punctuation">;</span>
            head <span class="token operator">=</span> head<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
            delNode<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">if</span> <span class="token punctuation">(</span>head <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token keyword">null</span><span class="token punctuation">;</span>

        <span class="token class-name">ListNode</span> prev <span class="token operator">=</span> head<span class="token punctuation">;</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span>prev<span class="token punctuation">.</span>next <span class="token operator">!=</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>prev<span class="token punctuation">.</span>next<span class="token punctuation">.</span>val <span class="token operator">==</span> val<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                <span class="token class-name">ListNode</span> delNode <span class="token operator">=</span> prev<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
                prev<span class="token punctuation">.</span>next <span class="token operator">=</span> delNode<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
                delNode<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span><span class="token keyword">else</span> <span class="token punctuation">{</span>
                prev <span class="token operator">=</span> prev<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">return</span> head<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><p>方法2：使用虚拟头节点</p> <div class="language-java extra-class"><pre class="language-java"><code><span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
    <span class="token keyword">public</span> <span class="token class-name">ListNode</span> <span class="token function">removeElements</span><span class="token punctuation">(</span><span class="token class-name">ListNode</span> head<span class="token punctuation">,</span> <span class="token keyword">int</span> val<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token class-name">ListNode</span> dummyHead <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">ListNode</span><span class="token punctuation">(</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        dummyHead<span class="token punctuation">.</span>next <span class="token operator">=</span> head<span class="token punctuation">;</span>
        <span class="token class-name">ListNode</span> prev <span class="token operator">=</span> dummyHead<span class="token punctuation">;</span>
        <span class="token keyword">while</span> <span class="token punctuation">(</span>prev<span class="token punctuation">.</span>next <span class="token operator">!=</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>prev<span class="token punctuation">.</span>next<span class="token punctuation">.</span>val <span class="token operator">==</span> val<span class="token punctuation">)</span> <span class="token punctuation">{</span>
                prev<span class="token punctuation">.</span>next <span class="token operator">=</span> prev<span class="token punctuation">.</span>next<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
            <span class="token punctuation">}</span><span class="token keyword">else</span> <span class="token punctuation">{</span>
                prev <span class="token operator">=</span> prev<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">return</span> dummyHead<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><h2 id="链表和递归"><a href="#链表和递归" class="header-anchor">#</a> 链表和递归</h2> <p>链表也是可以使用递归，因为链表本身就具备递归的性质，但是因为链表是一种线性结构，一般我们使用for循环就可以解决链表相关的问题。但是如果从链表就能深刻的打好递归的基础，可以为后面更深入的学习树这种结构打好基础。</p> <p>递归本质上就是将原来的问题，转化为更小的同一个问题。</p> <p>下面我们来举一个简单的例子：数组求和</p> <p>对于数组求和我们可以将它转化如下</p> <div class="language- extra-class"><pre class="language-text"><code>sum(arr[0, n-1]) = arr[0] + sum(arr[1, n-1]) // 转换为了一个更小的同一问题
sum(arr[1, n-1]) = arr[1] + sum(arr[2, n-1]) // 转换为了一个更小的同一问题
// 依次缩小到求一个元素的和
sum(arr[n-1, n-1]) = arr[n-1] + sum(arr[]) // 最后转化成了一个最基本的问题
</code></pre></div><p>对数组求和这个问题我们没有必要使用递归，但是使用递归的方式来实现数组求和这个问题是一个非常好的理解递归的开始，因为这个问题的逻辑非常简单，可以帮助我们更好的理解递归。</p> <div class="language-java extra-class"><pre class="language-java"><code><span class="token keyword">public</span> <span class="token keyword">class</span> <span class="token class-name">Sum</span> <span class="token punctuation">{</span>
  <span class="token comment">// 用户只需要传入一个int型的数组即可</span>
  <span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">int</span> <span class="token function">sum</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> arr<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">return</span> <span class="token function">sum</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>
  <span class="token comment">// 计算arr[l...n)这个区间内所有数字的和</span>
  <span class="token keyword">private</span> <span class="token keyword">static</span> <span class="token keyword">int</span> <span class="token function">sum</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> arr<span class="token punctuation">,</span> <span class="token keyword">int</span> l<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>l <span class="token operator">==</span> arr<span class="token punctuation">.</span>length<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>

    <span class="token keyword">return</span> arr<span class="token punctuation">[</span>l<span class="token punctuation">]</span> <span class="token operator">+</span> <span class="token function">sum</span><span class="token punctuation">(</span>arr<span class="token punctuation">,</span> l <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
  <span class="token punctuation">}</span>
  <span class="token comment">// 测试</span>
  <span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token class-name">String</span><span class="token punctuation">[</span><span class="token punctuation">]</span> args<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> nums <span class="token operator">=</span> <span class="token punctuation">{</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">6</span><span class="token punctuation">}</span><span class="token punctuation">;</span>
    <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token function">sum</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 21</span>
  <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><p>所有的递归算法都是可以分成两部分的，第一部分是求解这个最基本的问题，递归算法就是把原问题变成一个更小的问题，这个更小的问题可以变成更更小的问题，依次类推，直到原问题变成一个最基本的问题。在数组求和这个问题里<code>if (l == arr.length)</code>先判断下当前是不是一个最基本的问题，如果是的就返回0即可；第二部分是把原问题转化成更小的问题的过程。</p> <p>我们在写递归函数的时候一定要注重递归函数的&quot;宏观&quot;语义，对于sum函数来说就是计算arr[l,n)这个范围里所有元素的和。递归函数本身就是一个函数，完成一个功能，它和一个函数a里调用一个函数b是没什么本质区别，只不过在递归函数里函数b的名字是a而已。在数组求和这个例子中sum函数里调用sum，我们可以把调用的这个sum&quot;忘掉&quot;，我们可以假象成我们现在有一个子逻辑叫sum，这个子逻辑需要传两个参数arr和l，它做的事情就是计算arr这个数组中[l, n)这个范围内所有元素的和。在这种情况下写一段逻辑怎么计算arr数组中从[l, n)这个范围数组的和，同时要用上sum这个函数？其实就是求<code>arr[l] + sum(arr, l + 1)</code>。</p> <p>下图中的链表我们可以想象成0这个节点后面又挂了一个链表，对于链表来说我们可以把它理解成一个个节点的挂接，也可以理解成一个头接节点后面又挂载一个小的链表，依次类推，直到最后Null本身也可以当做一个链表。</p> <p><img src="" alt=""></p> <p>下面我们用递归来解决上面删除链表中元素的问题：</p> <p>对于最开始的链表我们可以理解成头节点就是e这个节点后面跟了一个更短的链表，假设现在我们有了一个函数这个函数可以递归删除这个小链表中所有值为val的节点，这样我们处理完这个小链表后，再判断头节点e的值是不是等于val，如果头节点的值不等于val，则将头节点和处理后的小链表拼接起来就得到了最终结果，如果头节点的值等于val，则这个处理后的小链表就是最终结果。</p> <p><img src="/assets/img/21.2335b5ba.png" alt=""></p> <div class="language-java extra-class"><pre class="language-java"><code><span class="token comment">/// Leetcode 203. Remove Linked List Elements</span>
<span class="token comment">/// https://leetcode.com/problems/remove-linked-list-elements/description/</span>

<span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>

    <span class="token keyword">public</span> <span class="token class-name">ListNode</span> <span class="token function">removeElements</span><span class="token punctuation">(</span><span class="token class-name">ListNode</span> head<span class="token punctuation">,</span> <span class="token keyword">int</span> val<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 整个链表为空</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>head <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span>
            <span class="token keyword">return</span> head<span class="token punctuation">;</span>
        <span class="token comment">// 把removeElements这个函数想成一个子过程，它的作用就是删除一个链表中值为val的节点，也就是删除head后面的小链表中值为val的节点，所以第一个参数传入head.next，第二个参数传入要删除的值。res存的是head后面小链表删除值为val节点后的结果</span>
        <span class="token class-name">ListNode</span> res <span class="token operator">=</span> <span class="token function">removeElements</span><span class="token punctuation">(</span>head<span class="token punctuation">.</span>next<span class="token punctuation">,</span> val<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token comment">// 判断head节点是否需要删除，如果head节点需要删除直接返回res</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>head<span class="token punctuation">.</span>val <span class="token operator">==</span> val<span class="token punctuation">)</span>
            <span class="token keyword">return</span> res<span class="token punctuation">;</span>
        <span class="token keyword">else</span><span class="token punctuation">{</span>
            <span class="token comment">// 头节点不需要删除，则将头节点和小链表连接起来</span>
            head<span class="token punctuation">.</span>next <span class="token operator">=</span> res<span class="token punctuation">;</span>
            <span class="token keyword">return</span> head<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 测试</span>
    <span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token class-name">String</span><span class="token punctuation">[</span><span class="token punctuation">]</span> args<span class="token punctuation">)</span> <span class="token punctuation">{</span>

        <span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> nums <span class="token operator">=</span> <span class="token punctuation">{</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">6</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">6</span><span class="token punctuation">}</span><span class="token punctuation">;</span>
        <span class="token class-name">ListNode</span> head <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">ListNode</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>head<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token class-name">ListNode</span> res <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token keyword">new</span> <span class="token class-name">Solution</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">removeElements</span><span class="token punctuation">(</span>head<span class="token punctuation">,</span> <span class="token number">6</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>res<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><p>从图中可以看到head.next指向的就是处理后的小链表，如果head的值等于val，则直接返回head.next即可；如果head的值不等于val，则返回head即可，通过head就可以找到处理后的小链表。所以上述代码还可以简化如下：</p> <div class="language-java extra-class"><pre class="language-java"><code><span class="token keyword">class</span> <span class="token class-name">Solution5</span> <span class="token punctuation">{</span>

    <span class="token keyword">public</span> <span class="token class-name">ListNode</span> <span class="token function">removeElements</span><span class="token punctuation">(</span><span class="token class-name">ListNode</span> head<span class="token punctuation">,</span> <span class="token keyword">int</span> val<span class="token punctuation">)</span> <span class="token punctuation">{</span>

        <span class="token keyword">if</span><span class="token punctuation">(</span>head <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">return</span> head<span class="token punctuation">;</span>

        head<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token function">removeElements</span><span class="token punctuation">(</span>head<span class="token punctuation">.</span>next<span class="token punctuation">,</span> val<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> head<span class="token punctuation">.</span>val <span class="token operator">==</span> val <span class="token operator">?</span> head<span class="token punctuation">.</span>next <span class="token operator">:</span> head<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token comment">// 测试</span>
    <span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token class-name">String</span><span class="token punctuation">[</span><span class="token punctuation">]</span> args<span class="token punctuation">)</span> <span class="token punctuation">{</span>

        <span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> nums <span class="token operator">=</span> <span class="token punctuation">{</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">6</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">6</span><span class="token punctuation">}</span><span class="token punctuation">;</span>
        <span class="token class-name">ListNode</span> head <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">ListNode</span><span class="token punctuation">(</span>nums<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>head<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token class-name">ListNode</span> res <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token keyword">new</span> <span class="token class-name">Solution5</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">removeElements</span><span class="token punctuation">(</span>head<span class="token punctuation">,</span> <span class="token number">6</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token class-name">System</span><span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span>res<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><h2 id="递归再深入"><a href="#递归再深入" class="header-anchor">#</a> 递归再深入</h2> <p>在前面介绍栈这种数据结构时，在介绍栈的应用时简单介绍了下程序调用的系统栈这种场景</p> <p><img src="/assets/img/19.2bb2e974.png" alt=""></p> <p>递归和上面这张图是一样的，以数组求和这个类似为例，只不过是把fn1和fn2换成了sum而已。</p> <p>下面我们来模拟下删除链表中值为val的的例子，至于数组求和的例子比较简单，大家可以自行模拟。</p> <p>从链表 3 -&gt; 4 -&gt; 5 -&gt; null 中删除值为4的节点</p> <p><img src="/assets/img/22.bc9d2394.png" alt=""></p> <p>图片中代码前的1、2、3表示的是代码执行到第几步。</p> <div class="language-java extra-class"><pre class="language-java"><code><span class="token keyword">public</span> <span class="token class-name">ListNode</span> <span class="token function">removeElements</span><span class="token punctuation">(</span><span class="token class-name">ListNode</span> head<span class="token punctuation">,</span> <span class="token keyword">int</span> val<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>head <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span>
        <span class="token keyword">return</span> head<span class="token punctuation">;</span>

    head<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token function">removeElements</span><span class="token punctuation">(</span>head<span class="token punctuation">.</span>next<span class="token punctuation">,</span> val<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> head<span class="token punctuation">.</span>val <span class="token operator">==</span> val <span class="token operator">?</span> head<span class="token punctuation">.</span>next <span class="token operator">:</span> head<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre></div><p>开始执行代码，removeElements第一次调用：</p> <p>执行第一步后，head的值是3，不等于空，开始执行第二步，head.next的值等于再调用一次removeElements的返回值，此时代码停到2等待第二次调用removeElements的结果；</p> <p>第二次调用removeElements，这次调用我们将head.next也就是以4这个节点为头结点的链表传给了removeElements，来尝试删除这个新链表的元素。执行代码第一行，看现在的这个head是否为空，4不为空，开始执行第二个步，head.next的值等于第三次调用removeElements的返回值，此时代码停到2这个位置等待第三次调用removeElements的结果；</p> <p>开始执行第三次调用removeElements函数，将head.next，也就是以5这个节点为头节点的链表传给removeElements，来尝试删除这个新链表的元素。执行代码第一行，看现在的这个head是否为空，5不为空，开始执行第二步，此时代码停到第二步等待第四次调用removeElements的结果；</p> <p>第四次调用removeElements函数，将head.next，也就是以null这个节点为头节点的链表传给removeElements，来尝试删除这个新链表的元素。执行代码第一行，看现在的这个head是否为空，null为空，将null返回给第三次调用removeElements的2的位置使得head.next = null，执行第三步，head.next也就是null不等于val，直接返回5-&gt;null这个链表给第二次调用removeElements的head.next，执行第三步，此时head.val = 4等于val，返回head.next，也就是5-&gt;null这个链表给第一次调用removeElements的head.next，执行第三步，head.val也就是3不等于val，直接返回head，得到最终结果：3 -&gt; 5 -&gt; null这个链表。</p> <p>递归调用是有代价的：</p> <p>函数的调用是有时间开销的，包括记录当前代码执行到哪里，当前变量的状态等压入栈，还包括函数调用本身在计算机的底层要找个这个新的函数所在的位置，这些都是有一定的时间消耗的。</p> <p>更重要的是递归调用是消耗系统栈的空间的，如果在递归调用中不处理最基本的那种情况也就是递归调用终止条件，递归调用就会一直进行下去，直到系统栈被沾满。</p> <h2 id="翻转链表"><a href="#翻转链表" class="header-anchor">#</a> 翻转链表</h2> <p>问题：</p> <div class="language- extra-class"><pre class="language-text"><code>反转一个单链表。

示例:

输入: 1-&gt;2-&gt;3-&gt;4-&gt;5-&gt;NULL
输出: 5-&gt;4-&gt;3-&gt;2-&gt;1-&gt;NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
</code></pre></div><ol><li>非递归实现
思路：</li></ol> <div class="language-java extra-class"><pre class="language-java"><code><span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
    <span class="token keyword">public</span> <span class="token class-name">ListNode</span> <span class="token function">reverseList</span><span class="token punctuation">(</span><span class="token class-name">ListNode</span> head<span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">public</span> <span class="token class-name">ListNode</span> <span class="token function">reverseList</span><span class="token punctuation">(</span><span class="token class-name">ListNode</span> head<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token class-name">ListNode</span> pre <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token class-name">ListNode</span> cur <span class="token operator">=</span> head<span class="token punctuation">;</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span>cur <span class="token operator">!=</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token class-name">ListNode</span> next <span class="token operator">=</span> cur<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
            cur<span class="token punctuation">.</span>next <span class="token operator">=</span> pre<span class="token punctuation">;</span>
            pre <span class="token operator">=</span> cur<span class="token punctuation">;</span>
            cur <span class="token operator">=</span> next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> pre<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><ol start="2"><li>递归实现
思路：</li></ol> <div class="language-java extra-class"><pre class="language-java"><code><span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
    <span class="token keyword">public</span> <span class="token class-name">ListNode</span> <span class="token function">reverseList</span><span class="token punctuation">(</span><span class="token class-name">ListNode</span> head<span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">public</span> <span class="token class-name">ListNode</span> <span class="token function">reverseList</span><span class="token punctuation">(</span><span class="token class-name">ListNode</span> head<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>head <span class="token operator">==</span> <span class="token keyword">null</span> <span class="token operator">||</span> head<span class="token punctuation">.</span>next <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">return</span> head<span class="token punctuation">;</span>

        <span class="token class-name">ListNode</span> node <span class="token operator">=</span> <span class="token function">reverseList</span><span class="token punctuation">(</span>head<span class="token punctuation">.</span>next<span class="token punctuation">)</span>
        head<span class="token punctuation">.</span>next<span class="token punctuation">.</span>next <span class="token operator">=</span> head<span class="token punctuation">;</span>
        head<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div></div> <footer class="page-edit"><!----> <!----></footer> <div class="page-nav"><p class="inner"><span class="prev">
      ←
      <a href="/front/算法和数据结构/常见数据结构/04.html" class="prev">
        队列
      </a></span> <!----></p></div> </main></div><div class="global-ui"><!----><!----></div></div>
    <script src="/assets/js/app.8c5a7a92.js" defer></script><script src="/assets/js/2.8e30e130.js" defer></script><script src="/assets/js/6.0db48d19.js" defer></script><script src="/assets/js/64.0323ed89.js" defer></script>
  </body>
</html>
